TY - GEN
T1 - Spectral graph sparsification in nearly-linear time leveraging efficient spectral perturbation analysis
AU - Feng, Zhuo
N1 - Publisher Copyright:
© 2016 ACM.
PY - 2016/6/5
Y1 - 2016/6/5
N2 - Spectral graph sparsification aims to find an ultra-sparse subgraph whose Laplacian matrix can well approximate the original Laplacian matrix in terms of its eigenvalues and eigenvectors. The resultant sparsified subgraph can be efficiently leveraged as a proxy in a variety of numerical computation applications and graph-based algorithms. This paper introduces a practically efficient, nearly-linear time spectral graph sparsification algorithm that can immediately lead to the development of nearly-linear time symmetric diagonally-dominant (SDD) matrix solvers. Our spectral graph sparsification algorithm can efficiently build an ultra-sparse subgraph from a spanning tree subgraph by adding a few "spectrally-critical" off-tree edges back to the spanning tree, which is enabled by a novel spectral perturbation approach and allows to approximately preserve key spectral properties of the original graph Laplacian. Extensive experimental results confirm the nearly-linear runtime scalability of an SDD matrix solver for large-scale, real-world problems, such as VLSI, thermal and finite-element analysis problems, etc. For instance, a sparse SDD matrix with 40 million unknowns and 180 million nonzeros can be solved (1E-3 accuracy level) within two minutes using a single CPU core and about 6GB memory.
AB - Spectral graph sparsification aims to find an ultra-sparse subgraph whose Laplacian matrix can well approximate the original Laplacian matrix in terms of its eigenvalues and eigenvectors. The resultant sparsified subgraph can be efficiently leveraged as a proxy in a variety of numerical computation applications and graph-based algorithms. This paper introduces a practically efficient, nearly-linear time spectral graph sparsification algorithm that can immediately lead to the development of nearly-linear time symmetric diagonally-dominant (SDD) matrix solvers. Our spectral graph sparsification algorithm can efficiently build an ultra-sparse subgraph from a spanning tree subgraph by adding a few "spectrally-critical" off-tree edges back to the spanning tree, which is enabled by a novel spectral perturbation approach and allows to approximately preserve key spectral properties of the original graph Laplacian. Extensive experimental results confirm the nearly-linear runtime scalability of an SDD matrix solver for large-scale, real-world problems, such as VLSI, thermal and finite-element analysis problems, etc. For instance, a sparse SDD matrix with 40 million unknowns and 180 million nonzeros can be solved (1E-3 accuracy level) within two minutes using a single CPU core and about 6GB memory.
KW - Iterative methods
KW - SDD matrix solver
KW - Spectral graph sparsification
UR - http://www.scopus.com/inward/record.url?scp=84977134596&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84977134596&partnerID=8YFLogxK
U2 - 10.1145/2897937.2898094
DO - 10.1145/2897937.2898094
M3 - Conference contribution
AN - SCOPUS:84977134596
T3 - Proceedings - Design Automation Conference
BT - Proceedings of the 53rd Annual Design Automation Conference, DAC 2016
T2 - 53rd Annual ACM IEEE Design Automation Conference, DAC 2016
Y2 - 5 June 2016 through 9 June 2016
ER -