Generalized “Compress and Eliminate” Method for Solving Linear Systems with Large Sparse Matrices

We propose a generalization of the ''Compress and eliminate'' algorithm for sparse triangular factorization and direct solution of the linear systems with sparse matrices. The initial algorithm is applicable only to symmetric positive definite sparse matrices, while our generalization extends its applicability to the case of non-symmetric sparse matrices with symmetric sparse structures, which significantly increases the applicability of the algorithm. The algorithm's main idea comprises block Gaussian elimination and compression of the non-zero blocks formed during the first step. With linear asymptotic as one of its key features, the developed algorithm outperforms in terms of memory and runtime efficiency classical and recent algorithms, such as LU-like and HSS solvers. We prove the algorithm’s efficiency theoretically and provide its Python realization.