Parallel methods for SLAE solution on the systems with distributed memory in Krylov library
DOI:
https://doi.org/10.14529/cmse120203Keywords:
iterative algorithms, domain decomposition methods, parallel computing, algebraic systems, sparse matrices, numerical experiments, additive Schwarz methodAbstract
The paper presents an approach to creation of black-box parallel iterative solver, which is used in Krylov library for solving systems of linear algebraic equations (SLAEs) with large sparse matrices in CSR format arising from discretization of multidimensional boundary value problems. A variant of one-dimensional algebraic decomposition method is offered. The algorithm is based on breadth-first search of SLAE’s adjacency graph that allows to reduce the matrix to block-tridiagonal form. The algebraic solver is based on additive Schwarz method which naturally suits distributed memory computer systems. The generalized minimal residual method is used to solve the SLAEs arising from relations on subdomains’ boundaries. Auxiliary subdomain systems are solved with Intel MKL’s multithreaded direct solver PARDISO. Implemented algorithms were tested on the numerical solution of the series of computational mathematics problems, such as problems of hydrodynamics, diffusion-convection equations, problems of electromagnetism and others. Adduced numerical experiments results show the effectiveness of the presented algorithms for multiprocessor computational systems with distributed memory.
References
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.
