Introduction
Solving massive, sparse systems of linear equations ($Ax = b$) is a foundational challenge in scientific computing, underpinning applications from structural engineering to weather forecasting. While Algebraic Multigrid (AMG) methods are highly efficient for well-behaved elliptic problems, they often struggle with indefinite systems or irregular meshes. Conversely, Incomplete LU (ILU) factorizations offer robustness but are notoriously difficult to parallelize across distributed-memory architectures.
This paper introduces parGeMSLR, a C++/MPI library designed to bridge this gap. By combining multilevel domain decomposition with a unique low-rank correction to the Schur complement, parGeMSLR provides a robust, scalable solver capable of leveraging both massive CPU clusters and GPU acceleration.
Methodology
The core of the library is the GeMSLR (Generalized Multilevel Schur complement Low-Rank) algorithm. Its architecture is built on three primary pillars:
1. Multilevel Partitioning
Unlike traditional Hierarchical Interface Decomposition (HID) methods that may suffer from load imbalance as the number of blocks fluctuates across levels, parGeMSLR employs a $p$-way vertex separator to recursively divide the matrix's adjacency graph. By maintaining a fixed number of $p$ partitions at every level, the library ensures superior load balancing across MPI processes, which is critical for performance on high-performance computing (HPC) clusters.
2. Schur Complement with Low-Rank Correction
The algorithm addresses the computational bottleneck of inverting the interface matrix (the Schur complement) by utilizing the Sherman-Morrison-Woodbury formula. Instead of a direct inversion, the inverse is approximated as the sum of a simple approximate inverse and a low-rank correction term. This correction is designed to capture the most significant eigenvalues that the initial approximation misses, effectively "bridging the gap" to ensure convergence even for difficult matrices.
3. Hybrid Parallelism and GPU Acceleration
parGeMSLR is built for modern heterogeneous environments. It uses MPI for inter-node communication and supports CUDA for the "solve phase." By offloading heavy-duty tasks—such as triangular substitutions and dense matrix-vector multiplications—to NVIDIA GPUs (e.g., V100), the library significantly reduces the time-to-solution for high-rank approximations.
Experimental Evaluation
The authors evaluated parGeMSLR against several challenging model problems:
- 3D Poisson Equation: Tested on regular grids and unstructured "crooked pipe" meshes to assess geometric flexibility.
- 3D Linear Elasticity: A cantilever beam model that becomes increasingly ill-conditioned based on material properties.
- 3D Helmholtz Equation: A notoriously difficult indefinite problem used in wave propagation where standard solvers often fail.
Key Results
- Scalability: The library demonstrated strong weak scaling, maintaining high efficiency on up to 1,024 MPI processes for a Poisson problem with 128 million unknowns. Strong scaling tests on a $320^3$ grid showed excellent speedup, though efficiency naturally tapers as communication latency increases with more levels.
- GPU Performance: Offloading the solve phase to GPUs yielded a 3.2x speedup over CPU-only versions for high-rank approximations.
- Robustness: In tests involving the indefinite Helmholtz equation, parGeMSLR successfully converged in scenarios where standard SchurILU methods failed entirely. It also outperformed AMG on nearly singular linear elasticity problems.
Discussion and Future Work
A critical insight from the study is the trade-off between communication and computation. While increasing the number of levels in the hierarchy reduces the computational work per level, it increases the frequency of MPI Allreduce operations. Finding the optimal number of levels is essential for maximizing throughput.
Currently, the "setup phase" (constructing the preconditioner) remains a CPU-bound bottleneck. Future development will focus on porting this phase to GPUs and implementing block Arnoldi or randomized subspace iterations to mitigate network latency during the low-rank term calculation. Despite the setup cost, parGeMSLR is highly effective in scenarios where the preconditioner can be amortized over multiple right-hand sides.
Conclusion
parGeMSLR represents a significant step forward in parallel sparse solvers. By integrating multilevel Schur complement techniques with low-rank corrections and hybrid CPU/GPU computing, it provides a scalable and robust solution for the most demanding linear systems in science and engineering.
Summary updated