Modified method of parallel matrix sweep
https://doi.org/10.29235/1561-2430-2019-55-4-425-434
Abstract
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.
About the Authors
A. A. Zgirouski
Belarusian State University
Russian Federation
Russian Federation
Andrei A. Zgirouski – Undergraduate
4, Nezavisimosti Ave., 220030, Minsk
N. A. Likhoded
Belarusian State University
Russian Federation
Russian Federation
Nikolai A. Likhoded – Dr. Sc. (Physics and Mathematics)
4, Nezavisimosti Ave., 220030, Minsk
References
1. Samarskii A. A., Nikolaev E. S. Numerical Methods for Grid Equations. Vol. 1. Direct Methods. Birkhauser Verlag, 1989. 242 p.
2. Heller 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
3. Akimova E. N. Parallelization of the matrix sweep algorithm. Matematicheskoe modelirovanie = Mathematical Models, 1994, vol. 6, no. 9,pp. 61–67 (in Russian).
4. 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).
5. Hirshman 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.049
6. Davina 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
7. 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).
8. Wang 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.355947
9. Buzbee 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/0707049
10. Austin T. M., Berndt M., Moulton J. D. A memory efficient parallel tridiagonal solver. Preprint LA-VR-03-4149, 2004. 13 p.
Review
Views: 916
Email this article 