SDSL-Solver: Scalable Distributed Sparse Linear Solvers for Large-Scale Interior Point Methods
This work addresses the computational bottleneck of solving sparse linear systems in large-scale optimization, offering scalable distributed solutions for interior point methods.
SDSL-Solver is a distributed sparse linear solver for interior point methods that uses Krylov subspace methods with preconditioning, achieving up to 97.54x speedup over PARDISO on single-node and 7.77x over PETSc on four-node clusters for problems with up to five million variables.
The solution of sparse linear systems constitutes the dominant computational bottleneck in interior point methods (IPMs), frequently consuming over 70\% of the total solution time. As optimization problems scale to millions of variables, direct solvers encounter prohibitive fill-in, excessive memory consumption, and limited parallel scalability. We present SDSL-Solver, a scalable distributed sparse linear solver framework designed for IPMs. SDSL-Solver employs Krylov subspace methods, combined with numerics-based sparse filtering and diagonal correction techniques that produce high-quality preconditioners. To accommodate diverse problem characteristics, SDSL-Solver offers two complementary distributed parallel methods: Block Jacobi for well-conditioned, diagonally dominant systems, and Bordered Block Diagonal (BBD) for ill-conditioned problems requiring globally coupled preconditioning via Schur complement techniques. A preconditioner reuse strategy further amortizes construction costs across consecutive IPMs iterations. We evaluate SDSL-Solver on benchmark problems with matrix dimensions ranging from tens of thousands to over five million on multi-node clusters equipped with X86 processors. The experimental results show that under the Block Jacobi and BBD distributed methods, SDSL-Solver on a four-node configuration achieves average speedups of $6.23\times$ and $7.77\times$, respectively, compared to PETSc running on the same number of nodes. Relative to the single-node PARDISO, the average speedups reach $97.54\times$ and $5.85\times$, respectively.