"Compress and eliminate" solver for symmetric positive definite sparse matrices

Daria A. Sushnikova, Ivan V. Oseledets

Abstract

The "Compress and Eliminate" (CE) solver introduces a novel approximate factorization for large, sparse symmetric positive definite (SPD) matrices. By combining block Gaussian elimination with low-rank compression, the CE algorithm strategically zeros out "fill-in" elements, achieving near-linear complexity. Experimental results on 3D diffusion problems demonstrate that CE outperforms state-of-the-art direct solvers like CHOLMOD by up to 10x in speed and memory efficiency.

Introduction

Solving linear systems $Ax = b$ derived from partial differential equations (PDEs) is a cornerstone of scientific computing. Researchers typically choose between robust direct solvers, such as Cholesky factorization, and efficient iterative solvers like Conjugate Gradient. However, direct solvers face a significant hurdle: "fill-in." As elimination progresses, zero entries in the sparse matrix become non-zero, leading to exponential growth in memory and computational requirements, particularly in 3D simulations. While hierarchical low-rank methods attempt to mitigate this, they often introduce high mathematical overhead. The "Compress and Eliminate" (CE) approach bridges this gap by maintaining sparsity through the compression of fill-in as it is generated.

The CE Algorithm

The CE algorithm operates through a multilevel process consisting of two primary stages per level: Compression and Elimination.

1. Compression

Prior to eliminating a block row, the algorithm classifies blocks into "close" and "far" zones. Far-zone blocks represent long-range interactions that are typically low-rank. A unitary transformation (essentially a basis rotation via SVD) is applied to these blocks to concentrate their information into a small rank. This allows the majority of the block to be treated as zero without significant loss of accuracy.

Classification of blocks into close and far zones within a block row.

2. Elimination

Standard block Gaussian elimination is performed on the remaining "close" blocks. Because the far-zone was previously compressed, the elimination step avoids the usual explosion of non-zero entries. Unlike standard incomplete Cholesky (ILU) methods which simply drop small entries, CE uses a mathematically rigorous transformation to create zeros while preserving the most important information.

The iterative CE process showing the transition from matrix $\hat{A}_{i-1}$ through the elimination process to the resulting matrix $\tilde{A}_i$.

The algorithm is multilevel; once a set of variables is eliminated, the remaining Schur complement is "coarsened" by grouping blocks into super-blocks, and the process repeats. The authors offer two variants: $CE(\epsilon)$, which adjusts rank dynamically for direct solving, and $CE(r)$, which uses a fixed rank as a fast preconditioner for iterative methods like MINRES.

Experimental Evaluation

The method was evaluated using synthetic systems from a 3D Diffusion Equation discretized on an equidistant cubic grid. This benchmark represents a common, demanding task in engineering and physics. Matrix sizes scaled up to $N = 131,072$ unknowns to demonstrate asymptotic performance.

Key Results

  • Efficiency vs. CHOLMOD: For large 3D systems, the $CE(r)$ solver was approximately 10 times faster and required 10 times less memory than CHOLMOD, an industry-standard direct solver.
  • Preconditioning Power: As a preconditioner for MINRES, the $CE(\epsilon)$ method reduced the number of iterations to a near-constant (4–6 iterations) regardless of problem scale. In contrast, standard ILUt preconditioners saw iteration counts explode as the problem scaled.
  • Linear Scaling: Memory requirements for the approximate factorization scaled almost linearly ($O(N^{1.1}$ to $O(N^{1.2})$), confirming the theoretical efficiency.

Conclusion and Future Work

The CE solver effectively exploits the "far-field" structure of PDE-based matrices to maintain sparsity by design. While highly efficient, the current algorithm assumes a known variable ordering based on grid geometry. Future work will focus on developing automated, geometry-agnostic ordering strategies and replacing the SVD bottleneck with cheaper rank-revealing factorizations like pivoted QR. Additionally, extending the method to non-symmetric or indefinite systems remains an open challenge.

Summary updated

BibTeX
@article{sushnikova2018compress,
  author = {Daria A. Sushnikova and Ivan V. Oseledets},
  title = {{"Compress and eliminate" solver for symmetric positive definite sparse matrices}},
  journal = {SIAM J. Scientific Computing},
  year = {2018},
  url = {https://openreview.net/forum?id=pF1ij5wNFsD},
}
Figure