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

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...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0278-0070
1937-4151
DOI:10.1109/TCAD.2021.3060647