Модифицированный метод параллельной матричной прогонки
https://doi.org/10.29235/1561-2430-2019-55-4-425-434
Аннотация
Тематика работы относится к области построения параллельных алгоритмов численного решения блочно-трехдиагональных систем линейных алгебраических уравнений. Такие системы часто возникают в приложениях и для ряда задач требуют использования высокопроизводительных многоядерных вычислительных систем. Один из широко применяемых на практике подходов к решению блочно-трехдиагональных систем заключается в использовании оригинальных алгоритмов параллельной матричной прогонки. В настоящей статье рассмотрен метод параллельной матричной прогонки, основанный на разбиении матрицы. Этот метод трехфазный: сначала исходная система разбивается на части и после независимых преобразований каждой из них составляется редуцированная блочно-трехдиагональная система, затем из этой системы находят несколько неизвестных каждой части уравнений, после чего независимо вычисляются остальные неизвестные каждой части. Предложена новая модификация метода; обосновано, что если для исходной системы уравнений справедливы известные (и часто выполненные на практике) условия устойчивости метода матричной прогонки, то вычисления разработанной модификации параллельной матричной прогонки являются устойчивыми.
Об авторах
А. А. Згировский
Белорусский государственный университет
Россия
Россия
Згировский Андрей Александрович – магистрант факультета прикладной математики и информатики.
пр. Независимости, 4, 220030, г. Минск
Н. А. Лиходед
Белорусский государственный университет
Россия
Россия
Лиходед Николай Александрович – доктор физико-математических наук, профессор кафедры вычислительной математики факультета прикладной математики и информатики.
пр. Независимости, 4, 220030, г. Минск
Список литературы
1. Самарский, А. А. Методы решения сеточных уравнений / А. А. Самарский, Е. С. Николаев. – М.: Наука, 1978. – 592 с.
2. Heller, D. Some aspects of the cyclic reduction algorithm for block tridiagonal linear systems / D. Heller // SIAM J. Numer. Anal.– 1976. – Vol. 13, №. 4. – P. 484–496. https://doi.org/10.1137/0713042
3. Акимова, Е. Н. Распараллеливание алгоритма матричной прогонки / Е. Н. Акимова // Математическое моделирование. – 1994. – Т. 6, № 9. – С. 61–67.
4. Акимова, Е. Н. Параллельные алгоритмы решения СЛАУ с блочно-трехдиагональными матрицами на многопроцессорных вычислителях / Е. Н. Акимова, Д. В. Белоусов // Вестн. УГАТУ. – 2011. – Т. 15, № 5. – С. 87–93.
5. BCYCLIC: A parallel block tridiagonal matrix cyclic solver / S. P. Hirshman [et al.] // J. Comput. Phys. – 2010. – Vol. 229, №. 18. – P. 6392–6404. https://doi.org/10.1016/j.jcp.2010.04.049
6. Davina, A. Lamas. MPI-CUDA parallel linear solvers for block-tridiagonal matrices in the context of SLEPc’seigensolvers/ A. Lamas Davina, J. E. Roman // Parallel Comput. – 2018.– Vol. 74. – P. 118–135. https://doi.org/10.1016/j.parco.2017.11.006
7. Об организации параллельных вычислений и «распараллеливании» прогонки / Н. Н. Яненко [и др.] // Численные методы механики сплошной среды. – 1978. – Т. 9, № 7. – С. 139–146.
8. Wang, H. H. A parallel method for tridiagonal equations / H. H. Wang / ACM Trans. Math.Software.–1981. – Vol. 7, № 2. – P. 170–183. https://doi.org/10.1145/355945.355947
9. Buzbee, B. L. On direct methods for solving Poisson’s equations / B. L. Buzbee, G. H. Golub, C. W. Nielson // SIAM J. Numer. Anal.– 1970. – Vol. 7, №. 4. – P. 627–656. https://doi.org/10.1137/0707049
10. Austin, T. M. A memory efficient parallel tridiagonal solver: Preprint LA-VR-03-4149 / T. M. Austin, M. Berndt, J. D. Moulton. – 2004. – 13 p.
Рецензия
Просмотров: 915
Послать статью по эл. почте 