feGRASS: Fast and Effective Graph Spectral Sparsification for Scalable Power Grid Analysis

• Published in: IEEE transactions on computer-aided design of integrated circuits and systems 2022-03, Vol.41 (3), p.681-694
• Main Authors: Liu, Zhiqiang, Yu, Wenjian, Feng, Zhuo
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation algorithms; Eigenvalues and eigenfunctions; Graph theory; Iterative solver; Laplace equations; low-stretch spanning tree (LSST); power grid analysis; Power grids; Resistance; Spectra; spectral graph sparsification; Symmetric matrices; Task analysis
• ISSN: 0278-0070; 1937-4151
• DOI: 10.1109/TCAD.2021.3060647

Graph spectral sparsification aims to find a ultrasparse subgraph which can preserve the spectral properties of the original graph. The subgraph can be leveraged to construct a preconditioner to speed up the solution of the original graph's Laplacian matrix. In this work, we propose feGRASS, a fast and effective graph spectral sparsification approach for the problem of large-scale power grid analysis and other problems with similar graphs. The proposed approach is based on two novel concepts: 1) effective edge weight and 2) spectral edge similarity. The former takes advantage of node degrees and breadth-first-search (BFS) distances, which leads to a scalable algorithm for generating low-stretch spanning trees (LSSTs). Then, the latter concept is leveraged during the recovery of spectrally critical off-tree edges to produce spectrally similar subgraphs. Compared with the most recent competitor [1] , the proposed approach is much faster for producing high-quality spectral sparsifiers. Extensive experimental results have been demonstrated to illustrate the superior efficiency of a preconditioned conjugate gradient (PCG) algorithm based on the proposed approach, for solving large power grid problems and many other real-world graph Laplacians. For instance, a power grid matrix with 60 million unknowns and 260 million nonzeros can be solved (at a 1E-3 accuracy level) within 196 s and 12 PCG iterations, on a single CPU core.