SAMG: Sparsified graph-theoretic algebraic multigrid for solving large symmetric diagonally dominant (SDD) matrices
SAMG: Sparsified graph-theoretic algebraic multigrid for solving large symmetric diagonally dominant (SDD) matrices
复制标题
DOI：
10.1109/iccad.2017.8203832
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Zhiqiang Zhao;Yongyu Wang;Zhuo Feng
中科院分区：
文献类型：
--
作者：
Zhiqiang Zhao;Yongyu Wang;Zhuo Feng
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.
