pGRASS-Solver: A Graph Spectral Sparsification-Based Parallel Iterative Solver for Large-Scale Power Grid Analysis

With the increase in the complexity of VLSI chips, power grid analysis has become a challenging task, because linear equations of extremely large size need to be solved. Recent graph sparsification-based solvers have shown promising performance for power grid analysis. However, existing graph sparsification algorithms are implemented in serial computing, while factorization and backward/forward substitution of the sparsifier’s Laplacian matrix are hard to parallelize. On the other hand, partition-based iterative methods which are inherently parallel lack a direct control of the relative condition number of the preconditioner and consume more memory. In this work, we propose a novel parallel iterative solver called pGRASS-Solver. We first propose a practically efficient parallel graph sparsification algorithm. Then, the domain decomposition method (DDM) is utilized to solve the sparsifier’s Laplacian matrix. To further improve the efficiency, a variant of DDM which employs partial Cholesky factorization and Schur complement matrix sparsification is proposed. Thus, we obtain an efficient parallel preconditioner, which not only leads to fast convergence but also enjoys ease of parallelization. Numerous experiments are conducted to illustrate the superior efficiency of the proposed pGRASS-Solver for large-scale power grid analysis, showing an average
$6.8\times $
speedup over a recent parallel iterative solver (Wang et al. 2017). Moreover, it solves a real-world power grid matrix with 0.36 billion nodes and 8.7 billion nonzeros within 20 min on a 16-core machine, which is
$10.9\times $
faster than the best result of sequential graph sparsification-based solver (Liu et al. 2022).