vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2019-55-4-425-434vestifm-471Research ArticleМАТЕМАТИКАMATHEMATICSМодифицированный метод параллельной матричной прогонкиModified method of parallel matrix sweepЗгировскийА. А.ZgirouskiA. A.

Згировский Андрей Александрович – магистрант факультета прикладной математики и информатики.

пр. Независимости, 4, 220030, г. Минск

 

Andrei A. Zgirouski – Undergraduate

4, Nezavisimosti Ave., 220030, Minsk

zgirovskya@gmail.comЛиходедН. А.LikhodedN. A.

Лиходед Николай Александрович – доктор физико-математических наук, профессор кафедры вычислительной математики факультета прикладной математики и информатики.

пр. Независимости, 4, 220030, г. Минск

 

Nikolai A. Likhoded – Dr. Sc. (Physics and Mathematics)

4, Nezavisimosti Ave., 220030, Minsk

likhoded@bsu.byБелорусский государственный университетBelarusian State University201907012020554425434Copyright © Згировский А.А., Лиходед Н.А., 20202020Згировский А.А., Лиходед Н.А.Zgirouski A.A., Likhoded N.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/471

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

The topic of this paper refers to efficient parallel solvers of block-tridiagonal linear systems of equations. Such systems occur in numerous modeling problems and require usage of high-performance multicore computation systems. One of the widely used methods for solving block-tridiagonal linear systems in parallel is the original block-tridiagonal sweep method. We consider the algorithm based on the partitioning idea. Firstly, the initial matrix is split into parts and transformations are applied to each part independently to obtain equations of a reduced block-tridiagonal system. Secondly, the reduced system is solved sequentially using the classic Thomas algorithm. Finally, all the parts are solved in parallel using the solutions of a reduced system. We propose a modification of this method. It was justified that if known stability conditions for the matrix sweep method are satisfied, then the proposed modification is stable as well.

параллельные вычисленияматричная прогонка блочно-трехдиагональных линейных системустойчивость параллельной матричной прогонкиparallel computationsblock-tridiagonal linear systems matrix sweepstability of parallel matrix sweepReferencesСамарский, А. А. Методы решения сеточных уравнений / А. А. Самарский, Е. С. Николаев. – М.: Наука, 1978. – 592 с.Samarskii A. A., Nikolaev E. S. Numerical Methods for Grid Equations. Vol. 1. Direct Methods. Birkhauser Verlag, 1989. 242 p.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/0713042Heller D. Some aspects of the cyclic reduction algorithm for block tridiagonal linear systems. SIAM Journal on Numerical Analysis. 1976, vol. 13, no. 4, pp. 484–496. https://doi.org/10.1137/0713042Акимова, Е. Н. Распараллеливание алгоритма матричной прогонки / Е. Н. Акимова // Математическое моделирование. – 1994. – Т. 6, № 9. – С. 61–67.Akimova E. N. Parallelization of the matrix sweep algorithm. Matematicheskoe modelirovanie = Mathematical Models, 1994, vol. 6, no. 9,pp. 61–67 (in Russian).Акимова, Е. Н. Параллельные алгоритмы решения СЛАУ с блочно-трехдиагональными матрицами на многопроцессорных вычислителях / Е. Н. Акимова, Д. В. Белоусов // Вестн. УГАТУ. – 2011. – Т. 15, № 5. – С. 87–93.Akimova E. N, Belousov D. V. Parallel algorithms for solving the systems of equations with block-three-diagonal matrices on multiprocessors computer systems. Vestnik UGATU[Scientific Journal of Ufa State Aviation Technical University], 2011 vol. 15, no. 5,pp. 87–93 (in Russian).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.049Hirshman S. P., Perumalla K. S., Lynch V. E., Sanchez R. BCYCLIC: A parallel block tridiagonal matrix cyclic solver. Journal of Computational Physics, 2010, vol. 229, no. 18, pp. 6392–6404. https://doi.org/10.1016/j.jcp.2010.04.049Davina, 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.006Davina A. Lamas, Roman J. E. MPI-CUDA parallel linear solvers for block-tridiagonal matrices in the context of SLEPc’seigensolvers. Parallel Computing, 2018, vol. 74, pp. 118–135. https://doi.org/10.1016/j.parco.2017.11.006Об организации параллельных вычислений и «распараллеливании» прогонки / Н. Н. Яненко [и др.] // Численные методы механики сплошной среды. – 1978. – Т. 9, № 7. – С. 139–146.Yanenko N. N., Konovalov A. N., Bugrov A. N., Shustov G. V. Organization of Parallel Computing and the Thomas Algorithm Parallelization. Chislennye metody mekhaniki sploshnoi sredy [Numerical Methods in Continuum Mechanics], 1978, vol. 9, no. 7,pp. 139–146 (in Russian).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.355947Wang H. H. A parallel method for tridiagonal equations. ACM Transactions on Mathematical Software, 1981, vol. 7, no. 2, pp. 170–183. https://doi.org/10.1145/355945.355947Buzbee, 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/0707049Buzbee B. L., Golub G. H., Nielson C. W. On direct methods for solving Poisson’s equations.SIAM Journal on Numerical Analysis, 1970, vol. 7, no. 4, pp. 627–656. https://doi.org/10.1137/0707049Austin, T. M. A memory efficient parallel tridiagonal solver: Preprint LA-VR-03-4149 / T. M. Austin, M. Berndt, J. D. Moulton. – 2004. – 13 p.Austin T. M., Berndt M., Moulton J. D. A memory efficient parallel tridiagonal solver. Preprint LA-VR-03-4149, 2004. 13 p.

The authors declare that there are no conflicts of interest present.