The efficiency comparison of solvers for sparse linear algebraic equations systems based on the BiCGStab and FGMRES methods
https://doi.org/10.15514/ISPRAS-2018-30(1)-13
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.
References
1. Saad Y. Iterative Methods for Sparse Linear Systems. N.Y.: PWS Publ., 1996. 547 p.
2. Schenk O., Gartner K. Solving unsymmetric sparse systems of linear equations with PARDISO // J. of Future Generation Computer Systems. 2004. № 20. P. 475–487.
3. PARDISO. URL: http://www.pardiso-project.org/ (accessed: 15.10.2017).
4. Intel® Math Kernel Library – Documentation. URL: https://software.intel.com/en-us/articles/intel-math-kernel-library-documentation (accessed: 15.10.2017).
5. Marchevsky I.K., Puzikova V.V. Efficiency investigation of computation parallelization for viscous incompressible flow simulation on systems with shared memory. Vychislitel'nye metody i programmirovanie [Computational methods and programming], 2015. Vol. 16. P. 595–606 (in Russian)
6. ANSYS All Products. URL: http://www.ansys.com/products/all-products (accessed: 15.10.2017).
7. MSC Nastran. URL: http://www.mscsoftware.ru/products/msc-nastran (accessed: 15.10.2017).
8. ANSYS Fluent. URL: http://www.ansys.com/Products/Fluids/ANSYS-Fluent (accessed: 15.10.2017).
9. STAR-CD. URL: https://mdx.plm.automation.siemens.com/star-cd (accessed: 15.10.2017).
10. OpenFOAM® Documentation. URL: https://www.openfoam.com/documentation/ (accessed: 15.10.2017).
11. What is KRATOS. URL: http://www.cimne.com/kratos/about_whatiskratos.asp (accessed: 15.10.2017).
12. AMGCL documentation. URL: http://amgcl.readthedocs.io/en/latest/ (accessed: 15.10.2017).
13. foam-extend. URL: https://sourceforge.net/projects/foam-extend/ (accessed: 15.10.2017).
14. Portable, Extensible Toolkit for Scientific Computation. URL: https://www.mcs.anl.gov/petsc/ (accessed: 15.10.2017).
15. Van der Vorst H.A. Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for solution of non-symmetric linear systems. SIAM J. Sci. Stat. Comp. 1992. № 2. P. 631–644.
16. Saad Y. A flexible inner-outer preconditioned GMRES algorithm. SIAM J. Sci. Comput. 1993. № 14. P. 461–469.
17. Balandin M.Yu., Shurina E.P. Metody reshenija SLAU bol'shoj razmernosti [Methods for large SLAE solving]Novosibirsk: NGTU publ., 2000. 70 p. (in Russian)
18. Wesseling P. An introduction to multigrid methods. Chichester: John Willey & Sons Ltd., 1991. 284 p.
19. Guilmineau E., Queutey P. А numerical simulation of vortex shedding from an oscillating circular. J. Fluid Struct. 2002. № 16. P. 773–794.
20. Cheny Y., Botella O. The LS-STAG method: A new immersed boundary/level-set method for the computation of incompressible viscous flows in complex moving geometries with good conservation properties. J.Comp. Phys.2010. №229. P.1043-1076.
21. Mittal R., Iaccarino G. Immersed boundary methods. Annu. Rev. Fluid Mech. 2005. № 37. P. 239–261.
22. Osher S., Fedkiw R.P. Level set methods and dynamic implicit surfaces. N. Y.: Springer, 2003. 273 p.
23. Marchevsky I.K., Puzikova V.V. The efficiency analysis of iterative methods for solving linear algebraic equations systems. Matematicheskoe modelirovanie i chislennye metody [Mathematical modeling and numerical methods], 2014. № 4. P. 37-52 (in Russian)
Review
For citations:
Marchevsky I.K., Puzikova V.V. The efficiency comparison of solvers for sparse linear algebraic equations systems based on the BiCGStab and FGMRES methods. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(1):195-214. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(1)-13
Email this article 