A Direct Elliptic Solver Based on Hierarchically Low-Rank Schur Complements

Gustavo Ivan Chavez Chavez; George Turkiyyah; David E. Keyes

doi:10.1007/978-3-319-52389-7_12

A Direct Elliptic Solver Based on Hierarchically Low-Rank Schur Complements

Gustavo Ivan Chavez Chavez, George Turkiyyah, David E. Keyes

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

A parallel fast direct solver for rank-compressible block tridiagonal linear systems is presented. Algorithmic synergies between Cyclic Reduction and Hierarchical matrix arithmetic operations result in a solver with O(Nlog2N) arithmetic complexity and O(NlogN) memory footprint. We provide a baseline for performance and applicability by comparing with well-known implementations of the $\mathcal{H}$ -LU factorization and algebraic multigrid within a shared-memory parallel environment that leverages the concurrency features of the method. Numerical experiments reveal that this method is comparable with other fast direct solvers based on Hierarchical Matrices such as $\mathcal{H}$ -LU and that it can tackle problems where algebraic multigrid fails to converge.

Original language	English (US)
Title of host publication	Domain Decomposition Methods in Science and Engineering XXIII
Publisher	Springer Nature
Pages	135-143
Number of pages	9
ISBN (Print)	9783319523880
DOIs	https://doi.org/10.1007/978-3-319-52389-7_12
State	Published - Mar 18 2017

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

Access to Document

10.1007/978-3-319-52389-7_12

Cite this

@inproceedings{fa1b9f99ee074873842d7d3574b1d1ee,

title = "A Direct Elliptic Solver Based on Hierarchically Low-Rank Schur Complements",

abstract = "A parallel fast direct solver for rank-compressible block tridiagonal linear systems is presented. Algorithmic synergies between Cyclic Reduction and Hierarchical matrix arithmetic operations result in a solver with O(Nlog2N) arithmetic complexity and O(NlogN) memory footprint. We provide a baseline for performance and applicability by comparing with well-known implementations of the $\mathcal{H}$ -LU factorization and algebraic multigrid within a shared-memory parallel environment that leverages the concurrency features of the method. Numerical experiments reveal that this method is comparable with other fast direct solvers based on Hierarchical Matrices such as $\mathcal{H}$ -LU and that it can tackle problems where algebraic multigrid fails to converge.",

author = "{Chavez Chavez}, {Gustavo Ivan} and George Turkiyyah and Keyes, {David E.}",

note = "KAUST Repository Item: Exported on 2020-10-01",

year = "2017",

month = mar,

day = "18",

doi = "10.1007/978-3-319-52389-7_12",

language = "English (US)",

isbn = "9783319523880",

pages = "135--143",

booktitle = "Domain Decomposition Methods in Science and Engineering XXIII",

publisher = "Springer Nature",

}

TY - GEN

T1 - A Direct Elliptic Solver Based on Hierarchically Low-Rank Schur Complements

AU - Chavez Chavez, Gustavo Ivan

AU - Turkiyyah, George

AU - Keyes, David E.

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2017/3/18

Y1 - 2017/3/18

N2 - A parallel fast direct solver for rank-compressible block tridiagonal linear systems is presented. Algorithmic synergies between Cyclic Reduction and Hierarchical matrix arithmetic operations result in a solver with O(Nlog2N) arithmetic complexity and O(NlogN) memory footprint. We provide a baseline for performance and applicability by comparing with well-known implementations of the $\mathcal{H}$ -LU factorization and algebraic multigrid within a shared-memory parallel environment that leverages the concurrency features of the method. Numerical experiments reveal that this method is comparable with other fast direct solvers based on Hierarchical Matrices such as $\mathcal{H}$ -LU and that it can tackle problems where algebraic multigrid fails to converge.

AB - A parallel fast direct solver for rank-compressible block tridiagonal linear systems is presented. Algorithmic synergies between Cyclic Reduction and Hierarchical matrix arithmetic operations result in a solver with O(Nlog2N) arithmetic complexity and O(NlogN) memory footprint. We provide a baseline for performance and applicability by comparing with well-known implementations of the $\mathcal{H}$ -LU factorization and algebraic multigrid within a shared-memory parallel environment that leverages the concurrency features of the method. Numerical experiments reveal that this method is comparable with other fast direct solvers based on Hierarchical Matrices such as $\mathcal{H}$ -LU and that it can tackle problems where algebraic multigrid fails to converge.

UR - http://hdl.handle.net/10754/623778

UR - http://link.springer.com/chapter/10.1007/978-3-319-52389-7_12

UR - http://www.scopus.com/inward/record.url?scp=85016206984&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-52389-7_12

DO - 10.1007/978-3-319-52389-7_12

M3 - Conference contribution

SN - 9783319523880

SP - 135

EP - 143

BT - Domain Decomposition Methods in Science and Engineering XXIII

PB - Springer Nature

ER -

A Direct Elliptic Solver Based on Hierarchically Low-Rank Schur Complements

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this