Сравнение эффективности решателей разреженных систем линейных алгебраических уравнений на основе методов BiCGStab и FGMRES

В данной работе проведено сравнение эффективности решателей разреженных систем линейных алгебраических уравнений, построенных на основе одних из наиболее быстрых итерационных методов, метода BiCGStab (метода бисопряженных градиентов со стабилизацией) и метода FGMRES (гибкого метода обобщенных минимальных невязок). В работе представлены оценки трудоемкости выполнения одной итерации рассматриваемых методов. Получено условие, которому должна удовлетворять размерность подпространства Крылова в методе FGMRES для того, чтобы трудоемкость одной итерации данного метода была меньше трудоемкости одной итерации метода BiCGStab. Кроме того представлена модификация метода FGMRES, позволяющая останавливать алгоритм до очередного рестарта в случае достижения заданной точности. На языке С++ на основе представленных алгоритмов методов BiCGStab и FGMRES (в том числе с ILU- и многосеточным предобуславливанием) разработаны решатели разреженных систем линейных алгебраических уравнений. Сравнение эффективности разработанных решателей проводилось на разностных аналогах уравнений Гельмгольца и Пуассона. Системы были взяты из тестовой задачи о моделировании обтекания кругового профиля, совершающего вынужденные поперечные колебания. Разностная схема для решения задачи строится на прямоугольной структурированной сетке интегро-интерполяционным методом LS-STAG - методом погруженных границ c функциями уровня. Вычислительные эксперименты показали, что метод FGMRES на задачах такого класса демонстрирует более высокую скорость сходимости по сравнению с методом BiCGStab. Время проведения расчета при использовании метода FGMRES сократилось более чем в 6.5 раз без предобуславливания и примерно в 3 раза с предобуславлванием. Реализация модифицированного алгоритма метода FGMRES также сравнивалась с аналогичным решателем из библиотеки Intel® Math Kernel Library. Вычислительные эксперименты показали, что разработанная реализация метода FGMRES позволила получить ускорение по сравнению с использованием Intel® MKL в 3.4 раза без предобуслвливания и в 1.4 раза при использовании ILU-предобуславливания.

разреженные системы линейных алгебраических уравнений, методы крыловского типа, метод BiCGStab, метод FGMRES, предобуславливание, многосеточный метод, уравнение Гельмгольца, уравнение Пуассона, метод погруженных границ LS-STAG, библиотека Intel Math Kernel Library

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. Марчевский И.К., Пузикова В.В. Исследование эффективности распараллеливания вычислений при моделировании течений вязкой несжимаемой среды методом LS-STAG на системах с общей памятью. Вычислительные методы и программирование. 2015. Т. 16. С. 595–606.

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. Баландин М.Ю., Шурина Э.П. Методы решения СЛАУ большой размерности. Новосибирск: Изд-во НГТУ, 2000. 70 с.

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. Марчевский И.К., Пузикова В.В. Анализ эффективности итерационных методов решения систем линейных алгебраических уравнений. Математическое моделирование и численные методы. 2014. № 4. С. 37–52.