Preview

Труды Института системного программирования РАН

Расширенный поиск

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

https://doi.org/10.15514/ISPRAS-2018-30(1)-13

Полный текст:

Аннотация

В данной работе проведено сравнение эффективности решателей разреженных систем линейных алгебраических уравнений, построенных на основе одних из наиболее быстрых итерационных методов, метода 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-предобуславливания.

Об авторах

И. К. Марчевский
МГТУ им. Н.Э. Баумана
Россия


В. В. Пузикова
МГТУ им. Н.Э. Баумана
Россия


Список литературы

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.


Для цитирования:


Марчевский И.К., Пузикова В.В. Сравнение эффективности решателей разреженных систем линейных алгебраических уравнений на основе методов BiCGStab и FGMRES. Труды Института системного программирования РАН. 2018;30(1):195-214. https://doi.org/10.15514/ISPRAS-2018-30(1)-13

For citation:


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

Просмотров: 327


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)