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

Zhiqiang Liu, Wenjian Yu, Zhuo Feng

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)681-694
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume41
Issue number3
DOIs
StatePublished - 1 Mar 2022

Keywords

  • Iterative solver
  • low-stretch spanning tree (LSST)
  • power grid analysis
  • spectral graph sparsification

Fingerprint

Dive into the research topics of 'FeGRASS: Fast and Effective Graph Spectral Sparsification for Scalable Power Grid Analysis'. Together they form a unique fingerprint.

Cite this