String-Wave Direct Parallel Solver for Sparse System of Linear Equations


  • Alexey Y. Likhosherstnyy APM Ltd., Korolev, Russian Federation; Belgorod State University, Belgorod, Russian Federation
  • Yana G. Velikaya Belgorod State University, Belgorod, Russian Federation



approximate minimum degree, string-wave algorithm, finite element method, system of linear equations, matrix factorization


The article discusses a parallel algorithm of solving linear algebraic equations systems for symmetric sparse matrices, which allows to split a large task into many small subtasks, thereby both increasing performance and reducing memory consumption. It is based on a method of simultaneous calculation of intermediate values during matrix factorization with maintaining load balancing on processors so that when the final result of the left parts of the factorization is obtained, the right parts of the factorization do not depend on them. This approach allows the initial stiffness matrix to be represented as a product of a large number of simple matrixes and solve a system of linear algebraic equations in the form of a sequence of solutions by substitution. To reduce the filling of sparse factorization matrices, an approximate minimum degree method was used, which, in addition to being one of the most efficient and fastest ones existing at the moment, allows the developed algorithm to distribute the load of calculations more evenly. The developed method is implemented in APM Ltd. software products for systems with shared memory, but it can also be performed for distributed memory systems.


Bathe, K.J., Wilson, E.L.: Numerical methods in finite element analysis. Stroyizdat, Moscow (1982).

Demmel, J.: Computational linear algebra. Theory and applications. Word, Moscow (2001).

Pissanetsky, S.: Sparse Matrix Technology. Academic Press Inc (1984).

Andreev, B.: Numerical methods. Publishing department of the Faculty of Computational Mathematics and Mathematics of Lomonosov Moscow State University, Moscow (2013).

Heggernes, P., Eisenstat, S.C., Kumfert, G.: The Computational Complexity of the Minimum Degree Algorithm. In: NASA/CR-2001-211421ICASE Report No. 2001-4, Langley Research Center, Hampton, Virginia (2001).

Voevodin, V., Voevodin, Vl.: Parallel Computing. BHV, Saint Petersburg (2002).

Gergel, V.P.: High-performance computing for multiprocessor, multi-core systems. Moscow University Publishing House, Moscow (2010).

Gergel, V.P.: Modern languages and parallel programming technologies. Moscow University Publishing House, Moscow (2012).




How to Cite

Likhosherstnyy, A. Y., & Velikaya, Y. G. (2024). String-Wave Direct Parallel Solver for Sparse System of Linear Equations. Supercomputing Frontiers and Innovations, 10(4), 21–26.