О вопросах распараллеливания крыловских итерационных методов

Валерий Павлович Ильин

Аннотация


В работе рассматриваются математические вопросы многообразных вычислительных технологий методов распараллеливания итерационных процессов крыловского типа для решения больших разреженных симметричных и несимметричных СЛАУ, возникающих при сеточных аппроксимациях многомерных краевых задач для систем дифференциальных уравнений. Характерным примером являются конечно-элементные приближения в газогидродинамических приложениях, где в каждом узле определены пять неизвестных функций, в силу чего СЛАУ имеет мелкоблочную структуру. Основой применяемых алгоритмов является гибкий метод обобщенных минимальных невязок FGMRES с динамическими предобуславливателями аддитивного типа, представляющий собой верхний уровень двухступенчатого итерационного алгоритма Шварца.
Для повышения производительности алгебраических решателей автором предлагается применение различных подходов: декомпозиции расчетной области с различными топологиями, типами краевых условий на смежных границах и размерами пересечений подобластей, методов грубосеточной коррекции и агрегации, дефляции и неполной факторизации матриц. Описываются унифицированные формулировки используемых алгоритмов, а также вопросы их вычислительной эффективности и масштабируемого распараллеливания на суперкомпьютерах гетерогенной архитектуры. Приводятся примеры технологических требований к особенностям программных реализаций библиотек параллельных алгоритмов для решения систем линейных алгебраических уравнений.

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


итерационные методы; подпространства Крылова; предобусловленные матрицы; декомпозиция областей; параллельные алгоритмы; программные и вычислительные технологии

Полный текст:

PDF

Литература


Ильин, В.П. Методы и технологии конечных элементов / В.П. Ильин. — Новосибирск: Изд-во ИВМиМГ СО РАН, 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 (дата обращения:

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/ (дата обращения:

02.2013).

Yousef Saad — SOFTWARE: URL: http://www.users.cs.umn.edu/~saad/software/ (дата обращения: 15.02.2013).




DOI: http://dx.doi.org/10.14529/cmse130303