О вопросах распараллеливания крыловских итерационных методов
Автор: Ильин Валерий Павлович
Статья в выпуске: 3 т.2, 2013 года.
Бесплатный доступ
В работе рассматриваются математические вопросы многообразных вычислительных технологий методов распараллеливания итерационных процессов крыловского типа для решения больших разреженных симметричных и несимметричных СЛАУ, возникающих при сеточных аппроксимациях многомерных краевых задач для систем дифференциальных уравнений. Характерным примером являются конечно-элементные приближения в газогидродинамических приложениях, где в каждом узле определены пять неизвестных функций, в силу чего СЛАУ имеет мелкоблочную структуру. Основой применяемых алгоритмов является гибкий метод обобщенных минимальных невязок FGMRES с динамическими предобуславливателями аддитивного типа, представляющий собой верхний уровень двухступенчатого итерационного алгоритма Шварца. Для повышения производительности алгебраических решателей автором предлагается применение различных подходов: декомпозиции расчетной области с различными топологиями, типами краевых условий на смежных границах и размерами пересечений подобластей, методов грубосеточной коррекции и агрегации, дефляции и неполной факторизации матриц. Описываются унифицированные формулировки используемых алгоритмов, а также вопросы их вычислительной эффективности и масштабируемого распараллеливания на суперкомпьютерах гетерогенной архитектуры. Приводятся примеры технологических требований к особенностям программных реализаций библиотек параллельных алгоритмов для решения систем линейных алгебраических уравнений.
Итерационные методы, подпространства крылова, предобусловленные матрицы, декомпозиция областей, параллельные алгоритмы, программные и вычислительные технологии
Короткий адрес: https://sciup.org/147160502
IDR: 147160502 | УДК: 519.6
On the questions of parallelized Krylov's iterative methods
Mathematical questions of various computational technologies of parallelelized iterative processes of Krylov’s type for solving large sparse symmetric and non-symmetric SLAEs, obtained in grid approximations of multi-dimensional boundary value problems for PDEs, are considered. Example are presented by finite approximations in gas-hydrodynamical applications, where five unknowns in each node are defined and corresponding SLAEs have small-block structure. The base of used algorithms is flexible generalized minimal residual, FGMRES, method with dynamical preconditioners of additive type, which presents an upper level of two-step iterarive Swartz algorithm. High performance of algebraic solvers is provided by using different approaches: domain decompositions of various topologies, boundary conditions and sizes of subdomain overlapping, coarse grid correction, deflation and aggregation, and incomplete factorizations of matrices. The unified formulations of using algorithms as well as the questions of computational efficiency and scalable parallelization at the geterogenous supercomputers are described. The examples of technical requirements for peculiarities of program implementation of the libraries of parallel algorithms for solving systems of linear algebraic equation, are presented.
Список литературы О вопросах распараллеливания крыловских итерационных методов
- Ильин, В.П. Методы и технологии конечных элементов/В.П. Ильин. -Новосибирск: Изд-во ИВМиМГ СО РАН, 2007.
- Лебедев, В.И. Вариационные алгоритмы метода разделения области/В.И. Лебедев, В.И. Агошков. -М., Препр. ОВМ РАН; № 54. -1983.
- Bramble, J.H. Convergence estimates for product iterative methods with applications to domain decomposition/J. Bramble, J. Pasciak, J. Wang, J. Xu//Math. Comp. -1991. -Vol. 57, № 195. -P. 1-21.
- Ильин, В.П. Параллельные методы и технологии декомпозиции областей./В.П. Ильин//Вестник ЮУрГУ. Серия «Вычислительная математика и информатика». -2012. -Вып. 1. -№. 46(305). -С. 31-44.
- Saad, Y. Iterative Methods for Sparse Linear Systems, Second Edition/Y. Saad. -SIAM, 2003.
- Krylov: библиотека алгоритмов и программ для решения СЛАУ/Д.С. Бутюгин, В.П. Ильин, Е.А. Ицкович и др.//Современные проблемы математического моделирования. Математическое моделирование, численные методы и комплексы программ. Сборник трудов Всероссийских научных молодёжных школ. Ростов-на-Дону: Изд-во Южного федерального университета, 2009. -С. 110-128.
- Ильин, В.П. Проблемы высокопроизводительных технологий решения больших разреженных СЛАУ/В.П. Ильин//Вычислительные методы и программирование. -М., МГУ. -2009. -Т. 10, № 1. -C. 141-147.
- Бутюгин, Д.С. Методы параллельного решения СЛАУ на системах с распределенной памятью в библиотеке Krylov/Д.С. Бутюгин, В.П. Ильин, Д.В. Перевозкин//Вестник ЮУрГУ. Серия «Вычислительная математика и информатика». -2012. -Т. 47, № 306. -С. 5-19.
- Intel Math Kernel Library from Intel. URL: http://software.intel.com/sites/products/documentation/doclib/mkl_sa/11/mklman/index.htm (дата обращения: 15.02.2013).
- Ильин, В.П. Параллельные методы декомпозиции в пространствах следов/В.П. Ильин, Д.В. Кныш//Вычислительные методы и программирование. -2011. -Т. 12, № 1. -С. 100-109.
- Brezina, M. An improved convergence analysis of smoothed aggregation algebraic multigrid/M. Brezina, P. Vanek, P.S. Vassilevsky//Numer. Linear Algebra Appl. -2012. -Vol. 19. -P. 441-469.
- Farhat, C. FETI-DP: A dual-primal unified FETI method. Part I: A faster alternative to the two-level FETI method/C. Farhat, M. Lesoinne, P. LeTollei, K. Pierson, D. Rixen//Int. J. Numer. Math. Engrg. -2001. -Vol. 50. -P. 1523-1544.
- Кластер НКС-30Т: URL: http://www2.sscc.ru/HKC-30T/HKC-30T.htm (дата обращения: 15.02.2013).
- Message Passing Interface at Open Directory Project: URL: http://www.dmoz.org/Computers/Parallel_Computing/Programming/Libraries/MPI/(дата обращения: 15.02.2013).
- Малышкин, В.Э. Параллельное программирование мультикомпьютеров/В.Э. Малышкин, В.Д. Корнеев//Новосибирск: Изд. НГТУ, 2006.
- CUDA Tools & Ecosystem: URL: http://developer.nvidia.com/cuda-tools-ecosystem (дата обращения: 15.02.2013).
- Bell, N. CUSP: Generic parallel algorithms for sparse matrix and graph computations/N. Bell, M. Garland//URL: http://cusp-library.googlecode.com (дата обращения: 15.02.2013).
- Karypis, G. A fast and high quality multilevel scheme for partitioning irregular graphs/G. Karypis, V. Kumar//SIAM J. Sci. Comp. -1999. -Vol. 20, № 1. -P. 359-392.
- Hypre: URL: http://acts.nersc.gov/hypre/(дата обращения: 15.02.2013).
- PETSc: Home Page: URL: http://www.mcs.anl.gov/petsc/(дата обращения: 15.02.2013).
- Yousef Saad -SOFTWARE: URL: http://www-users.cs.umn.edu/~saad/software/(дата обращения: 15.02.2013).
