TY - GEN
T1 - SAMG
T2 - 36th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2017
AU - Zhao, Zhiqiang
AU - Wang, Yongyu
AU - Feng, Zhuo
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/12/13
Y1 - 2017/12/13
N2 - Algebraic multigrid (AMG) is a class of high-performance linear solvers based on multigrid principles. Compared to geometric multigrid (GMG) solvers that rely on the geometric information of underlying problems, AMG solvers build hierarchical coarse level problems according to the input matrices. Graph-theoretic Algebraic Multigrid (AMG) algorithms have emerged for solving large Symmetric Diagonally Dominant (SDD) matrices by taking advantages of spectral properties of graph Laplacians. This paper proposes a Sparsified graph-theoretic Algebraic Multigrid (SAMG) framework that allows efficiently constructing nearly-linear sized graph Laplacians for coarse level problems while maintaining good spectral approximation during the AMG setup phase by leveraging a scalable spectral graph sparsification engine. Our experimental results show that the proposed method can offer more scalable performance than existing graph-theoretic AMG solvers for solving large SDD matrices in integrated circuit (IC) simulations, 3D-IC thermal analysis, image processing, finite element analysis as well as data mining and machine learning applications.
AB - Algebraic multigrid (AMG) is a class of high-performance linear solvers based on multigrid principles. Compared to geometric multigrid (GMG) solvers that rely on the geometric information of underlying problems, AMG solvers build hierarchical coarse level problems according to the input matrices. Graph-theoretic Algebraic Multigrid (AMG) algorithms have emerged for solving large Symmetric Diagonally Dominant (SDD) matrices by taking advantages of spectral properties of graph Laplacians. This paper proposes a Sparsified graph-theoretic Algebraic Multigrid (SAMG) framework that allows efficiently constructing nearly-linear sized graph Laplacians for coarse level problems while maintaining good spectral approximation during the AMG setup phase by leveraging a scalable spectral graph sparsification engine. Our experimental results show that the proposed method can offer more scalable performance than existing graph-theoretic AMG solvers for solving large SDD matrices in integrated circuit (IC) simulations, 3D-IC thermal analysis, image processing, finite element analysis as well as data mining and machine learning applications.
KW - Algebraic multigrid
KW - Graph Laplacian matrix
KW - Graph sparsification
KW - Spectral graph theory
UR - http://www.scopus.com/inward/record.url?scp=85043508388&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85043508388&partnerID=8YFLogxK
U2 - 10.1109/ICCAD.2017.8203832
DO - 10.1109/ICCAD.2017.8203832
M3 - Conference contribution
AN - SCOPUS:85043508388
T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
SP - 601
EP - 606
BT - 2017 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2017
Y2 - 13 November 2017 through 16 November 2017
ER -