Труды Института системного программирования РАН (Oct 2018)
The efficiency comparison of solvers for sparse linear algebraic equations systems based on the BiCGStab and FGMRES methods
Abstract
The efficiency comparison of solvers for sparse linear algebraic equations systems based on one of the fastest iterative methods, the BiCGStab method (bi-conjugate gradient method with stabilization), and the FGMRES method (flexible method of generalized minimal residuals) is presented in this study. Estimates of computational cost per one iteration are presented for the considered methods. The condition imposed on the Krylov subspace dimensionality in the FGMRES is obtained. When this condition is fulfilled, the computational cost per one iteration of the FGMRES method is less than the computational cost per one iteration of the BiCGStab. In addition, the FGMRES modification, which allows to stop the algorithm before the next restart in case of achieving the specified accuracy, is presented. Solvers on the basis of presented the BiCGStab and FGMRES methods algorithms including ILU and multigrid preconditioning are developed on the C++ language for sparse linear algebraic equations systems. The efficiency comparison of developed solvers was carried out on the difference analogs of the Helmholtz and Poisson equations. The systems were taken from the test problem about simulation of the flow around a circular profile, which makes forced transverse oscillations. The difference scheme for the problem solution is constructed by the LS-STAG method (immersed boundaries method with level-set functions). Computational experiments showed that the FGMRES demonstrates a higher convergence rate on problems of this class in comparison with the BiCGStab. The FGMRES usage allowed to reduce the computation time by more than 6.5 times without preconditioning and more than 3 times with preconditioning. The implementation of the modified FGMRES algorithm was also compared with a similar solver from the Intel® Math Kernel Library. Computational experiments showed that the developed FGMRES implementation allowed to obtain acceleration in comparison with Intel® MKL by 3.4 times without preconditioning and by 1.4 times with ILU-preconditioning.
Keywords
