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

Abstract

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.