SAMG: Sparsified graph-theoretic algebraic multigrid for solving large symmetric diagonally dominant (SDD) matrices

Zhiqiang Zhao, Yongyu Wang, Zhuo Feng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

16 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication2017 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2017
Pages601-606
Number of pages6
ISBN (Electronic)9781538630938
DOIs
StatePublished - 13 Dec 2017
Event36th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2017 - Irvine, United States
Duration: 13 Nov 201716 Nov 2017

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
Volume2017-November
ISSN (Print)1092-3152

Conference

Conference36th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2017
Country/TerritoryUnited States
CityIrvine
Period13/11/1716/11/17

Keywords

  • Algebraic multigrid
  • Graph Laplacian matrix
  • Graph sparsification
  • Spectral graph theory

Fingerprint

Dive into the research topics of 'SAMG: Sparsified graph-theoretic algebraic multigrid for solving large symmetric diagonally dominant (SDD) matrices'. Together they form a unique fingerprint.

Cite this