Методы параллельного решения СЛАУ на системах с распределенной памятью в библиотеке Krylov
Аннотация
параллельного решателя, использованный в библиотеке Krylov для систем линейных алгебраических уравнений (СЛАУ) с разреженными матрицами высокого порядка, возникающими при сеточных аппроксимациях многомерных краевых задач и представленными в сжатом строчном формате CSR. Предлагается вариант алгебраической одномерной декомпозиции СЛАУ. Алгоритм основан на обходе в ширину графа матрицы системы и позволяет привести ее к блочно-трехдиагональному виду. За основу алгебраического решателя системы взят аддитивный метод Шварца, который естественным образом ложится на архитектуру вычислительных систем с распределенной памятью. Полученные алгебраические системы в подпространстве следов, образованных переменными на внутренних границах подобластей, решаются с помощью обобщенного метода минимальных невязок. Вспомогательные системы в подобластях решаются с помощью прямого алгоритма PARDISO из библиотеки Intel MKL, использующего распараллеливание над общей памятью средствами OpenMP. Реализованные алгоритмы апробированы на численном решении ряда задач вычислительной математики, таких как задачи гидродинамики, диффузионно-конвективные уравнения, задачи электромагнетизма и др. Приведенные результаты численных экспериментов демонстрируют эффективность предлагаемых решений для многопроцессорных вычислительных систем с распределенной памятью.
Ключевые слова
Полный текст:
PDFЛитература
Karypis, G. A Fast and Highly Quality Multilevel Scheme for Partitioning Irregular Graphs / G. Karypis, V. Kumar // SIAM Journal on Scientific Computing. – 1999. – Vol. 20, № 1. – P. 359–392.
Saad, Y. Iterative Methods for Sparse Linear Systems, Second Edition. / Y. Saad. –SIAM, 2003.
Intel (R) Math Kernel Library from Intel: сайт. URL: http://software.intel.com/en-us/articles/intel-mkl/ (дата обращения: 03.11.2012).
Eigen: сайт. URL: http://eigen.tuxfamily.org/index.php?title=Main_Page(дата обращения: 03.11.2012).
Ильин, В.П. Krylov: библиотека алгоритмов и программ для решения СЛАУ /В.П. Ильин, Д.С. Бутюгин, Е.А. Ицкович и др. // Современные проблемы математического моделирования. Математическое моделирование, численные методы и комплексы программ. Сборник трудов Всероссийских научных молодежных школ. – Ростов-на-Дону: Изд-во Южного федерального университета, 2009. – С. 110–128.
Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. – М: МЦНМО: БИНОМ. Лаборатория знаний, 2004.
Ильин, В.П. Методы и технологии конечных элементов. / В.П. Ильин. – Новосибирск: Изд-во ИВМиМГ СО РАН, 2007.
Кластер НКС-30Т: сайт. URL: http://www2.sscc.ru/HKC-30T/HKC-30T.htm (дата обращения: 03.11.2012).
Monk, P. Finite Element Methods for Maxwell’s Equations. / P. Monk. – Oxford University Press, 2003.
Ingelstrom, P. A new set of H(curl)-conforming hierarchical basis functions for tetrahedral meshes / P. Ingelstrom // IEEE Transactions on Microwave Theory and Techniques. – 2006. – Vol. 54, № 1. – P. 160–114.
DOI: http://dx.doi.org/10.14529/cmse120203