Решатели слау с блочно-ленточными матрицами

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

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

параллельные вычисления; кэш-промахи; системы линейных алгебраических уравнений.

Литература

1. Гун, В.C. Система построения двумерных ортогональных сеток общего назначения / В.С. Гун, В.С. Морозова, В.Л. Поляцко // Математическое моделирование. - 2017. - Т. 29, № 11. - С. 71-88.
2. Fang Chen. Updated Preconditioned Hermitian and Skew-Hermitian Splitting-Type Iteration Methods for Solving Saddle-Point Problems / Fang Chen, Tian-Yi Li, Kang-Ya Lu // Computational and Applied Mathematics. - 2020. - V. 39. - Article ID: 162. - 10 p.
3. Оптимизирующая распараллеливающая система. - URL: www.ops.rsu.ru (дата обращения 05.08.2021).
4. Козин, Р.Г. Алгоритмы численных методов линейной алгебры и их программная реализация / Р.Г. Козин. - М.: НИЯУ МИФИ, 2012.
5. Graham, S.L. Getting up to Speed: The Future of Supercomputing / S.L. Graham, M. Snir, C.A. Patterson. - Washington: National Academies Press, 2005.
6. Писсанецки, C. Технология разреженных матриц / C. Писсанецки. - М.: Мир, 1988.
7. Gill, P.E. On the Stability of Cholesky Factorization for Symmetric Quasidefinite Systems / P.E. Gill, A.S. Sauders, J.R. Shinnerl // SIAM Journal on Matrix Analysis and Applications. - 1996. - V. 17, № 1. - P. 35-46.
8. Allen, R. Optimizing Compilers for Modern Architectures: A Dependence-Based Approach / R. Allen, K. Kennedy. - San Francisco: Morgan Kaufmann Publisher, 2002.
9. Евстигнеев, В.А. Оптимизирующие преобразования в распараллеливающих компиляторах / В.А. Евстигнеев, В.Н. Касьянов // Программирование. - 1996. - № 6. - C. 12-26.
10. Muchnick, S. Advanced Compiler Design Implementation / S. Muchnick. - San Francisco: Morgan Kaufmann Publisher, 1997.
11. Steinberg, O.B. Parallelization of Recurrent Loops Due to the Preliminary Computation of Superpositions / O.B. Steinberg // Вестник ЮУрГУ. Серия: Математическое моделирование и программирование. - 2020. - Т. 13, № 3. - С. 59-67.