Solvers for Systems of Linear Algebraic Equations with Block-Band Matrices

The article proposes methods for constructing fast solvers for systems of linear algebraic equations with block-band matrices. A data structure for efficient storage of such matrices in RAM and a fast algorithm for solving systems of linear equations with such matrices based on this structure are proposed. The article is focused on the creation of solvers based on iterative algorithms for solving systems of linear equations with both symmetric matrices and matrices having a saddle-point singularity. It is proposed to develop and use a special precompiler to speed up the solver. The experimental solver is implemented in C, and the preliminary compilation is based on the Optimizing Parallelizing System in this paper. The results of numerical experiments that demonstrate high efficiency of the developed methods, including the efficiency of the precompiler, are presented.

Keywords

concurrent computing; cache misses; systems of linear algebraic equations.

References

1. Gun V.S., Morozova V.S., Polyaczko V.L. The General Purpose System for Construction of Two-Dimensional Orthogonal Grids. Matematicheskoe modelirovanie, 2017, vol. 29, no. 11, pp. 71-88. (in Russian)
2. Fang Chen, Tian-Yi Li, Kang-Ya Lu. Updated Preconditioned Hermitian and Skew-Hermitian Splitting-Type Iteration Methods for Solving Saddle-Point Problems. Computational and Applied Mathematics, 2020, vol. 39, article ID: 162, 10 p. DOI: 10.1007/s40314-020-01187-7
3. Optimizing Parallelizing System (2016). Available at: www.ops.rsu.ru (accessed 05.08.2021)
4. Kozin R.G. Algoritmy chislennyx metodov lineynoy algebry i ix programmnaya realizaciya [Algorithms of Numerical Methods of Linear Algebra and Their Software Implementation], Moscow, NIYaU MIFI, 2012. (in Russian)
5. Graham, S.L., Snir M., Patterson C.A. Getting up to Speed: the Future of Supercomputing, Washington, National Academies Press, 2005.
6. Pissaneczki S. Texnologiya razrezhennyx matricz [Sparse Matrix Technology], Moscow, Mir, 1988. (in Russian)
7. Gill, P.E., Sauders A.S., Shinnerl J.R. On the Stability of Cholesky Factorization for Symmetric Quasidefinite Systems. SIAM Journal on Matrix Analysis and Applications, 1996, vol. 17, no. 1, pp. 35-46.
8. Allen, R. Optimizing Compilers for Modern Architectures: a Dependence-Based Approach, San Francisco, Morgan Kaufmann Publisher, Academic Press, 2002.
9. Evstigneev V.A., Kas'yanov V.N. [Optimizing Conversions in Parallelizing Compilers]. Programmirovanie, 1996, no. 6, pp. 12-26. (in Russian)
10. Muchnick S. Advanced Compiler Design Implementation, San Francisco, Morgan Kaufmann Publisher, 1997.
11. Steinberg O.B. Parallelization of Recurrent Loops Due to the Preliminary Computation of Superpositions. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2020, vol. 13, no. 3, pp. 59-67. DOI: 10.14529/mmp200305