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.
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 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