MPI+OpenMP реализация метода BiCGStab с явным предобусловливанием для решения разреженных систем линейных алгебраических уравнений
DOI:
https://doi.org/10.26089/NumMet.v20r445Ключевые слова:
итерационное решение систем линейных уравнений, разреженные матрицы, неполное обратное треугольное разложение, параллельное предобусловливание, стабилизированный метод бисопряженных градиентов (BiCGStab)Аннотация
Для предобусловливания несимметричной положительно определенной разреженной матрицы рассматривается ее приближенная обратная, представленная в виде произведения нижнетреугольной и верхнетреугольной матриц. Предлагается новый способ предобусловливания положительно определенной разреженной матрицы- метод блочного Якоби неполного обратного LU-разложения. Описан алгоритм параллельной реализации метода BiCGStab с предложенным предобусловливанием с применением MPI+OpenMP-технологии. Проводится сравнение времени решения тестовых задач из коллекции разреженных матриц SuiteSparse (ранее известной как коллекция университета Флориды) методом BiCGStab с предложенным предобусловливанием и с предобусловливанием Якоби, а также с предобусловливанием блочного Якоби в сочетании с неполным треугольным разложением без заполнения. При этом используются разработанные параллельные реализации на основе MPI- или MPI+OpenMP-подходов.
Библиографические ссылки
- Капорин И.Е. О предобусловливании метода сопряженных градиентов при решении дискретных аналогов дифференциальных задач // Дифференциальные уравнения. 1990. 26, № 7. 1225-1236.
- Kaporin I.E. New convergence results and preconditioning strategies for the conjugate gradient method // Numer. Linear Algebra Appl. 1994. Vol. 1, N 2. 179-210.
- Капорин И.Е., Милюкова О.Ю. Неполное обратное треугольное разложение в параллельных алгоритмах предобусловленного метода сопряженных градиентов. Препринт № 037 ИПМ им. М.В. Келдыша. М., 2017.
- Капорин И.Е., Милюкова О.Ю. MPI+OpenMP параллельная реализация метода сопряженных градиентов с некоторыми явными предобусловливателями. Препринт № 008 ИПМ им. М.В. Келдыша. М., 2018.
- Капорин И.Е., Милюкова О.Ю. MPI+OpenMP реализация метода сопряженных градиентов с факторизованными явными предобусловливателями // Вопросы атомной науки и техники. Серия математическое моделирование физических процессов. 2018. Вып. 4. 57-69.
- Davis T.A., Hu Y. The university of Florida sparse matrix collection // ACM Trans. on Math. Software. 2011. Vol. 38, N 1. doi 10.1145/2049662.2049663.
- Капорин И.Е., Милюкова О.Ю. Массивно-параллельный алгоритм предобусловленного метода сопряженных градиентов для численного решения систем линейных алгебраических уравнений // Сб. Трудов отдела проблем прикладной оптимизации ВЦ РАН. М.: Изд-во ВЦ РАН, 2011. 132-157.
- Knight P.A. The Sinkhorn-Knopp algorithm: convergence and applications // SIAM J. Matrix Anal. Appl. 2008. Vol. 30, N 1. 261-275.
- Капорин И.Е. Итерационное решение систем линейных уравнений с использованием неполной обратной треугольной факторизации // Прямые и обратные задачи математической физики. М.: Изд-во МГУ, 1991. 71-77.
- Kershaw D.S. The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations // Journal of Computational Physics. 1978. Vol. 26, N 1. 43-65.
- Anzt H., Huckle T.K., Brackle J., Dongarra J. Incomplete sparse approximate inverses for parallel preconditioning // Parallel Computing. 2018. Vol. 71. 1-22.
- Van der Vorst H.A. Bi-CGStab: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems // SIAM J. Sci. Stat. Comput. 1992. Vol. 13, N 2. 631-644.
- Chan T.F., Szeto T. Composite step product methods for solving nonsymmetric linear systems // SIAM Journal on Scientific Computing. 1996. Vol. 17, N 6. 1491-1508.
- Saad Y., Schultz M.H. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems // SIAM Journal on Scientific and Statistical Computing. 1986. Vol. 7, N 3. 856-869.
- Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. М.: Мир, 1984.
- Капорин И.Е. Локализация собственных значений пучка положительно-определенных матриц // Ж. вычисл. матем. и матем. физ. 2008. 48, № 11. 1923-1931.
- Капорин И.Е., Милюкова О.Ю. MPI+OpenMPI реализация метода BiCGStab c факторизованным явным предобусловливателем. Препринт № 047 ИПМ им. М.В. Келдыша. М., 2019.