DOI: https://doi.org/10.26089/NumMet.v16r109

Параллельное формирование предобусловливателя, основанного на аппроксимации обращения Шермана-Моррисона

Авторы

  • Н.С. Недожогин
  • C.П. Копысов
  • А.К. Новиков

Ключевые слова:

линейные системы уравнений
явное предобусловливание
формула Шермана-Моррисона
параллельные вычисления
графические ускорители

Аннотация

Исследуются возможности ускорения предобусловленных методов бисопряженных градиентов (BiCGStab, Bi-Conjugate Gradient Stabilized) с предобусловливателем на основе аппроксимации обращения матрицы по формуле Шермана-Моррисона. Рассмотрена новая форма параллельного алгоритма, использующая матрично-векторные произведения при формирования матриц предобусловливателя. Показана эффективность распараллеливания наиболее ресурсоемких операций этого предобусловливателя на графических процессорах.

Новые вычислительные технологии

Загрузки

Опубликован

2015-02-26

Выпуск

Том 16 (2015): Выпуск 1.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

Н.С. Недожогин

Институт механики Уральского отделения РАН (ИМ УрО РАН)
ул. Т. Барамзиной, 34, 426067, Ижевск
• младший научный сотрудник

C.П. Копысов

Институт механики Уральского отделения РАН (ИМ УрО РАН)
ул. Т. Барамзиной, 34, 426067, Ижевск
• заведующий лабораторией

А.К. Новиков

Институт механики Уральского отделения РАН (ИМ УрО РАН)
ул. Т. Барамзиной, 34, 426067, Ижевск
• старший научный сотрудник

Библиографические ссылки

  1. Y. Saad, Iterative Methods for Sparse Linear Systems (SIAM, Philadelphia, 2003).
  2. R. Li and Y. Saad, “GPU-Accelerated Preconditioned Iterative Linear Solvers,” J. Supercomput. 63 (2), 443-466 (2013).
  3. M. Benzi, “Preconditioning Techniques for Large Linear Systems: A Survey,” J. Comput. Phys. 182 (2), 418-477 (2002).
  4. L. Yu. Kolotilina and A. Yu. Yeremin, “Factorized Sparse Approximate Inverse Preconditionings I: Theory,” SIAM J. Matrix Anal. Appl. 14 (1), 45-58 (1993).
  5. M. J. Grote and T. Huckle, “Parallel Preconditioning with Sparse Approximate Inverses,” SIAM J. Sci. Comput. 18 (3), 838-853 (1997).
  6. R. Bru, J. Cerdán, J. Marín, and J. Mas, “Preconditioning Sparse Nonsymmetric Linear Systems with the Sherman-Morrison Formula,” SIAM J. Sci. Comput. 25 (2), 701-715 (2003).
  7. J. Sherman and W. J. Morrison, “Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix,” Ann. Math. Stat. 21 (1), 124-127 (1950).
  8. N. S. Nedozhogin, A. S. Sarmakeeva, and S. P. Kopysov, “Sherman-Morrison High-Performance Algorithm for Matrix Inversion on GPU,” Vestn. South Ural Univ., Ser.: Vychisl. Mat. Inform. 3 (2), 101-108 (2014).
  9. S. Kopysov, I. Kuzmin, N. Nedozhogin, et al., “Scalable Hybrid Implementation of the Schur Complement Method for Multi-GPU Systems,” J. Supercomput. 69 (1), 81-88 (2014).
  10. S. P. Kopysov, I. M. Kuzmin, N. S. Nedozhogin, et al., “Parallel Implementation of a Finite-Element Algorithms on a Graphics Accelerator in the Software Package FEStudio,” Komp’yut. Issled. Model. 6 (1), 79-97 (2014).