MPI+OPENMP РЕАЛИЗАЦИЯ МЕТОДА СОПРЯЖЕННЫХ ГРАДИЕНТОВ С ПРЕДОБУСЛОВЛИВАТЕЛЕМ БЛОЧНОГО НЕПОЛНОГО ОБРАТНОГО ТРЕУГОЛЬНОГО РАЗЛОЖЕНИЯ ПЕРВОГО ПОРЯДКА (2022)
В работе рассматривается предобусловливатель блочного неполного обратного треугольного разложения первого порядка “по значению” BIIC-IC1 для решения систем линейных алгебраических уравнений с симметричной положительно определенной матрицей. Рассматривается способ применения MPI+OpenMP технологии для построения и обращения предобусловливателя BIIC-IC1, при этом в предобусловливателе число блоков кратно числам используемых процессоров и используемых потоков. Предлагается способ применения MPI+OpenMP технологии для построения и обращения предобусловливателя BIIC-IC1, в котором для применения OpenMP технологии используется специальное упорядочение узлов сетки внутри подобластей, соответствующих расчетам на процессорах. Проводится сравнение времени решения задач методом сопряженных градиентов с предобусловливателем BIIC-IC1 с использованием MPI и гибридной MPI+OpenMP технологии на примере модельной задачи и ряда задач из коллекции разреженных матриц SuiteSparse.
Идентификаторы и классификаторы
- eLIBRARY ID
- 49432450
Проблеме использования высокоуровнего параллелизма (мелкозернистого или распараллеливания алгоритма на потоки) при построении и обращении неявного факторизованного предобусловливателя посвящен ряд работ. В работах [19–22] было предложено использовать несколько итераций Якоби или блочного Якоби для решения треугольных систем при применении предобусловливания неполного треугольного разложения, что позволило получить высокий уровень параллелизма. В работе [23] предложен безытерационный способ применения MPI+OpenMP технологии при обращении неявного факторизованного предобусловливателя, т.е. решении двух треугольных систем (в том числе для случая решения СЛАУ (1)). В работе [24] предложен новый итерационный алгоритм вычисления предобусловливателей IC(0) (неполного треугольного разложения Холецкого без заполнения), IC(1), IC(2) (неполного треугольного разложения Холецкого с заполнением 1 и 2), в котором все ненулевые элементы треугольных матриц могут быть вычислены асинхронно.
Список литературы
- I. E. Kaporin, “New Convergence Results and Preconditioning Strategies for the Conjugate Gradient Method”, Numer. Linear Algebra Appl. 1 (2), 179-210 (1994). EDN: XMFKBG
- I. E. Kaporin, “A Preconditioned Conjugate-Gradient Method for Solving Discrete Analogs of Differential Problems”, Differ. Uravn. 26 (7), 1225-1236 (1990) [Differ. Equ. 26 (7), 897-906 (1990)].
- O. Yu. Milyukova, MPI+OpenMP Parallel Implementation of Conjugate Gradient Method with Preconditioner of Block Partial Inverse Triangular Decomposition of IC2S and IC1, Preprint No. 48 (Keldysh Institute of Applied Mathematics, Moscow, 2021). DOI: 10.20948/prepr-2021-48 EDN: TVMNCO
- N. Munksgaard, “Solving Sparse Symmetric Sets of Linear Equations by Preconditioned Conjugate Gradients”, ACM Trans. Math. Softw. 6 (2), 206-219 (1980).
- A. D. Tuff and A. Jennings, “An Iterative Method for Large Systems of Linear Structural Equations”, Int. J. Numer. Methods Eng. 7 (2), 175-183 (1973).
- M. A. Ajiz and A. Jennings, “A Robust Incomplete Choleski-Conjugate Gradient Algorithm”, Int. J. Numer. Methods Eng. 20 (5), 949-966 (1984).
- I. E. Kaporin, “High Quality Preconditionings of a General Symmetric Positive Definite Matrix Based on Its UTU+UTR+RTU-Decomposition”, Numer. Linear Algebra Appl. 5 (6), 483-509 (1998). EDN: LEZKXL
- I. E. Kaporin, Preconditioning of Systems of Linear AlgebraicEquations. Doctoral Dissertation in Mathematics and Physics (Moscow State Univ., Moscow, 2011). EDN: QFKXOV
- I. E. Kaporin and I. N. Kon’shin, “Parallel Solution of Symmetric Positive Definite Systems Based on Decomposition into Overlapping Blocks”, Zh. Vychisl. Mat. Mat. Fiz. 41 (4), 515-528 (2001) [Comput. Math. Math. Phys. 41 (4), 481-493 (2001)]. EDN: LGPBTH
-
I. E. Kaporin and O. Yu. Milyukova, "Massively Parallel Preconditioned Conjugate Gradient Algorithm for the Numerical Solution of Linear Algebraic Equations", in Optimization and Applications (Comput. Center Ross. Akad. Nauk, Moscow, 2011), Issue 2, pp. 32-49. -
I. S. Duff and G. A. Meurant, "The Effect of Ordering on Preconditioned Conjugate Gradients", BIT Numer. Math. 29, 635-657 (1989). -
S. Doi, "On Parallelism and Convergence of Incomplete LU Factorizations", Appl. Numer. Math. 7 (5), 417-436 (1991). DOI: 10.1016/0168-9274(91)90011-N -
Y. Notay, "An Efficient Parallel Discrete PDE Solver", Parallel Comput. 21 (11), 1725-1748 (1995). DOI: 10.1016/0167-8191(96)80005-6 EDN: AQPUOJ -
O. Yu. Milyukova, "Parallel Approximate Factorization Method for Solving Discrete Elliptic Equations", Parallel Comput. 27 (10), 1365-1379 (2001). DOI: 10.1016/S0167-8191(01)00092-8 EDN: LGZGER -
O. Yu. Milyukova, "Parallel Iterative Methods Using Factorized Preconditioning Matrices for Solving Elliptic Equations on Triangular Grids", Zh. Vychisl. Mat. Mat. Fiz. 46 (6), 1096-1113 (2006) [Comput. Math. Math. Phys. 46 (6), 1044-1060 (2006)]. DOI: 10.1134/S096554250606011X EDN: HTTSVP -
D. Hysom and A. Pothen, "A Scalable Parallel Algorithm for Incomplete Factor Preconditioning", SIAM J. Sci. Comput. 22 (6), 2194-2215 (2001). DOI: 10.1137/S1064827500376193 -
M. Magolu monga Made and H. A. van der Vorst, "Spectral Analysis of Parallel Incomplete Factorizations with Implicit Pseudo-Overlap", Numer. Linear Algebra Appl. 9 (1), 45-64 (2002). DOI: 10.1002/nla.247 -
O. Yu. Milyukova, "Combination of Numerical and Structured Approaches to the Construction of a Second-Order Incomplete Triangular Factorization in Parallel Preconditioning Methods", Zh. Vychisl. Mat. Mat. Fiz. 56 (5), 711-729 (2016) [Comput. Math. Math. Phys. 56 (5), 699-716 (2016)]. DOI: 10.1134/S096554251605016X EDN: VYMALV -
E. C. Anderson and Y. Saad, "Solving Sparse Triangular Systems on Parallel Computers", Int. J. High Speed Comput. 1, 73-96 (1989). -
S. W. Hammond and R. Schreiber, "Efficient ICCG on a Shared Memory Multiprocessor", Int. J. High Speed Comput. 4 (01), 1-21 (1992). DOI: 10.1142/S0129053392000183 -
M. M. Wolf, M. A. Heroux, and E. G. Boman, "Factors Impacting Performance of Multithreaded Sparse Triangular Solve", in Lecture Notes in Computer Science (Springer, Heidelberg, 2011), Vol. 6449, pp. 32-44. DOI: 10.1007/978-3-642-19328-6_6 -
E. Chow, H. Anzt, J. Scott, and J. Dongarra, "Using Jacobi Iterations and Blocking for Solving Sparse Triangular Systems in Incomplete Factorization Preconditioning", J. Parallel Distrib. Comput. 119, 219-230 (2018). DOI: 10.1016/j.jpdc.2018.04.017 -
E. Chow and A. Patel, "Fine-Grained Parallel Incomplete LU Factorization", SIAM J. Sci. Comput. 37 (2), 169-193 (2015). DOI: 10.1137/140968896 -
S. Cayrols, I. Duff, and F. Lopes, Parallelization of the Solve Phase in a Task-based Cholesky Solver Using a Sequential Task Flow Model, Technical Report RAL-TR-2018-008 (Harwell, Oxford, 2018). -
I. E. Kaporin and O. Yu. Milyukova, MPI+OpenMP Parallel Implementation of Explicitly Preconditioned Conjugate Gradient Method, Preprint No. 8 (Keldysh Institute of Applied Mathematics, Moscow, 2018). DOI: 10.20948/prepr-2018-8 EDN: VTRPAD -
I. E. Kaporin and O. Yu. Milyukova, "MPI+OpenMP Parallel Implementation of the Conjugate Gradient Method with Factorized Explicit Preconditioners", Voprosy Atomn. Nauki Tekhniki, Ser.: Mat. Mod. Fiz. Proc. Issue 4, 57-69 (2018). -
E. Chow, "Parallel Implementation and Practical Use of Sparse Approximate Inverse Preconditioners with a Priori Sparsity Patterns", Int. J. High Perform. Comput. Appl. 15 (1), 56-74 (2001). DOI: 10.1177/109434200101500106 EDN: LXASZR -
O. Yu. Milyukova, MPI+OpenMP Parallel Implementation of Conjugate Gradient Method with Factorized Preconditioner, Preprint No. 31 (Keldysh Institute of Applied Mathematics, Moscow, 2020). DOI: 10.20948/prepr-2020-31 EDN: WFTXVZ -
O. Yu. Milyukova, MPI+OpenMP Parallel Implementation of Conjugate Gradient Method with the Block Jacobi Preconditioner Combined with IC1, Preprint No. 83 (Keldysh Institute of Applied Mathematics, Moscow, 2020). DOI: 10.20948/prepr-2020-83 -
O. Yu. Milyukova, "MPI+OpenMP Parallel Implementation of Conjugate Gradient Method with Factored Implicit Preconditioners", Mat. Model. 33 (10), 19-38 (2021). DOI: 10.20948/mm-2021-10-02 EDN: UWVLJU -
O. Yu. Milyukova, Approaches MPI+OpenMP Implementation of Conjugated Gradient Method with Pre-conditioner of Block Incomplete Inverse Triangular Decomposition of IC1, Preprint No. 2 (Keldysh Institute of Applied Mathematics, Moscow, 2022). DOI: 10.20948/prepr-2022-2 EDN: UODDEA -
I. E. Kaporin and O. Yu. Milyukova, Incomplete Inverse Triangular Factorization in Parallel Algorithms of Preconditioned Conjugate Gradient Methods, Preprint No. 37 (Keldysh Institute of Applied Mathematics, Moscow, 2017). DOI: 10.20948/prepr-2017-37 EDN: YPIXIL -
T. A. Davis and Y. Hu, "The University of Florida Sparse Matrix Collection", ACM Trans. Math. Softw. 38 (1), 1: 1-1: 25 (2011). DOI: 10.1145/2049662.2049663 -
O. Axelsson, Iterative Solution Methods (Cambridge Univ. Press, New York, 1994). -
I. E. Kaporin, "Using Chebyshev Polynomials and Approximate Inverse Triangular Factorizations for Preconditioning the Conjugate Gradient Method", Zh. Vychisl. Mat. Mat. Fiz. 52 (2), 179-204 (2012) [Comput. Math. Math. Phys. 52 (2), 169-193 (2012)]. DOI: 10.1134/S0965542512020091 EDN: OPTDYT
Выпуск
Методы и алгоритмы вычислительной математики и их приложения.
Параллельные программные средства и технологии.
Другие статьи выпуска
Высокотемпературные эффекты оказывают существенное влияние на характеристики летательных аппаратов, движущихся с гиперзвуковой скоростью. В связи со сложностью постановки физического эксперимента, методы математического моделирования играют важную роль для нахождения характеристик гиперзвуковых летательных аппаратов. Обсуждается построение и реализация математической модели, предназначенной для численного моделирования гиперзвукового обтекания тела с учетом неравновесных физико-химических процессов в высокотемпературном воздухе. Математическая модель включает в себя уравнения газовой динамики, уравнения модели турбулентности и уравнения химической кинетики. Проводится численное моделирование сверх- и гиперзвукового обтекания полусферы потоком воздуха с учетом высокотемпературных эффектов. Приводится критический обзор различных моделей, которые применяются для нахождения расстояния от фронта ударной волны до поверхности сферы. Результаты расчетов, полученные с использованием разработанного численного метода, сравниваются с данными физического эксперимента и расчетными данными, имеющимися в литературе, в широком диапазоне чисел Маха набегающего потока. Разработанная модель и результаты расчетов имеют значение для моделирования обтекания тел сложной конфигурации и проектирования высокоскоростных летательных аппаратов.
The objective of this paper is to construct a generalized quadratic spectrum approximation based on the Kantorovich projection method which llows us to deal with the spectral pollution problem. For this purpose, we prove that the property U (see Eq. 3) holds under weaker conditions than the norm and the collectively compact convergence. Numerical results illustrate the effectiveness and the convergence of our method.
В данной работе начальная форма волны цунами (ниже именуемая источником цунами) представляется как решение обратной задачи математической физики на основе инверсии удаленных записей пришедшей волны, что позволяет детально изучить факторы, влияющие на результаты восстановления. Исследуемая задача является некорректной, что приводит к ожидаемой неустойчивости численного решения, существенно уменьшить которую позволяет регуляризация, основанная на методе усеченного сингулярного разложения (SVD) (далее метод r-решения). В рамках предложенного подхода на основе анализа распространения энергии олны предлагается методика выбора наиболее информативной части имеющейся системы наблюдения для реального события цунами на Соломоновых островах 6 февраля 2013 г. Метод может быть полезен при разработке новых систем мониторинга цунами.
Работа связана с изучением нелинейных параболических систем, возникающих при моделировании и управлении нестационарными процессами фильтрации в подземной гидродинамике. Одна из постановок является системой, которая включает в себя краевую задачу второго рода для квазилинейного параболического уравнения с неизвестной функцией источника в правой части, а также уравнение изменения по времени этой функции. В другой постановке рассматривается проблема управления этой системой с управляющим воздействием граничного режима. Данные постановки существенно отличаются от обычных краевых задач и задач управления для параболических уравнений, в которых предполагается, что все входные данные должны быть заданы. Полученные в работе результаты представляют не только теоретический интерес, они имеют практическое значение для исследования различных фильтрационных процессов. Приведены некоторые примеры таких приложений, связанных с движением жидкости в трещиновато-пористых средах.
Разработан алгоритм высокоточного численного решения эллиптического уравнения второго порядка при наличии в области нескольких интерфейсов, в том числе пересекающихся и невыпуклых. Для аппроксимации задачи в окрестности интерфейсов используются нерегулярные ячейки (н-ячейки), отсекаемые ими от регулярных ячеек прямоугольной сетки, и законтурные части этих ячеек. Для построения приближенного решения предложено: 1) выписывать дополнительные условия согласования в н-ячейках на интерфейсах, увеличивая количество согласуемых ячеек вблизи интерфейсов; 2) уменьшать общую часть интерфейса, заключенную в соседних ячейках и используемую для записи условий. Для решения краевой задачи Дирихле реализован hp-вариант метода коллокации и наименьших квадратов (hp-МКНК) в сочетании с современными алгоритмами ускорения итерационного процесса: предобуславливание; распараллеливание с помощью OpenMP; ускорение, основанное на подпространствах Крылова; многосеточный алгоритм. При решении различных тестовых задач исследованы сходимость hp-МКНК и обусловленность возникающих переопределенных систем линейных алгебраических уравнений (СЛАУ). Проведено сравнение результатов, полученных МКНК, с результатами других авторов, использовавших метод MIB (англ. matched interface and boundary).
Издательство
- Издательство
- МГУ
- Регион
- Россия, Москва
- Почтовый адрес
- оссийская Федерация, 119991, Москва, Ленинские горы, д. 1
- Юр. адрес
- оссийская Федерация, 119991, Москва, Ленинские горы, д. 1
- ФИО
- Садовничий Виктор Антонович (РЕКТОР)
- E-mail адрес
- info@rector.msu.ru
- Контактный телефон
- +7 (495) 9391000
- Сайт
- https://msu.ru/