A Parallel Sweeping Preconditioner for Heterogeneous 3D Helmholtz Equations

Jack Poulson; Björn Engquist; Siwei Li; Lexing Ying

doi:10.1137/120871985

A Parallel Sweeping Preconditioner for Heterogeneous 3D Helmholtz Equations

Jack Poulson, Björn Engquist, Siwei Li, Lexing Ying

Research output: Contribution to journal › Article › peer-review

54 Scopus citations

Abstract

A parallelization of a sweeping preconditioner for three-dimensional Helmholtz equations without large cavities is introduced and benchmarked for several challenging velocity models. The setup and application costs of the sequential preconditioner are shown to be O(γ2N4/3) and O(γN logN), where γ(ω) denotes the modestly frequency-dependent number of grid points per perfectly matched layer. Several computational and memory improvements are introduced relative to using black-box sparse-direct solvers for the auxiliary problems, and competitive runtimes and iteration counts are reported for high-frequency problems distributed over thousands of cores. Two open-source packages are released along with this paper: Parallel Sweeping Preconditioner (PSP) and the underlying distributed multifrontal solver, Clique. © 2013 Society for Industrial and Applied Mathematics.

Original language	English (US)
Pages (from-to)	C194-C212
Number of pages	1
Journal	SIAM Journal on Scientific Computing
Volume	35
Issue number	3
DOIs	https://doi.org/10.1137/120871985
State	Published - May 2 2013
Externally published	Yes

Access to Document

10.1137/120871985

Cite this

@article{43c1686a379947daa4f747667b0ea6ad,

title = "A Parallel Sweeping Preconditioner for Heterogeneous 3D Helmholtz Equations",

abstract = "A parallelization of a sweeping preconditioner for three-dimensional Helmholtz equations without large cavities is introduced and benchmarked for several challenging velocity models. The setup and application costs of the sequential preconditioner are shown to be O(γ2N4/3) and O(γN logN), where γ(ω) denotes the modestly frequency-dependent number of grid points per perfectly matched layer. Several computational and memory improvements are introduced relative to using black-box sparse-direct solvers for the auxiliary problems, and competitive runtimes and iteration counts are reported for high-frequency problems distributed over thousands of cores. Two open-source packages are released along with this paper: Parallel Sweeping Preconditioner (PSP) and the underlying distributed multifrontal solver, Clique. {\textcopyright} 2013 Society for Industrial and Applied Mathematics.",

author = "Jack Poulson and Bj{\"o}rn Engquist and Siwei Li and Lexing Ying",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: This work was partially supported by the sponsors of the Texas Consortium for Computational Seismology.The second author was supported by NSF grant DMS-1016577. The fourth author was supported by NSF CAREER grant DMS-0846501, NSF grant DMS-1016577, and funding from KAUST.This author was supported by a CAM fellowship. This publication acknowledges KAUST support, but has no KAUST affiliated authors.",

year = "2013",

month = may,

day = "2",

doi = "10.1137/120871985",

language = "English (US)",

volume = "35",

pages = "C194--C212",

journal = "SIAM Journal on Scientific Computing",

issn = "1064-8275",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - A Parallel Sweeping Preconditioner for Heterogeneous 3D Helmholtz Equations

AU - Poulson, Jack

AU - Engquist, Björn

AU - Li, Siwei

AU - Ying, Lexing

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: This work was partially supported by the sponsors of the Texas Consortium for Computational Seismology.The second author was supported by NSF grant DMS-1016577. The fourth author was supported by NSF CAREER grant DMS-0846501, NSF grant DMS-1016577, and funding from KAUST.This author was supported by a CAM fellowship. This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2013/5/2

Y1 - 2013/5/2

N2 - A parallelization of a sweeping preconditioner for three-dimensional Helmholtz equations without large cavities is introduced and benchmarked for several challenging velocity models. The setup and application costs of the sequential preconditioner are shown to be O(γ2N4/3) and O(γN logN), where γ(ω) denotes the modestly frequency-dependent number of grid points per perfectly matched layer. Several computational and memory improvements are introduced relative to using black-box sparse-direct solvers for the auxiliary problems, and competitive runtimes and iteration counts are reported for high-frequency problems distributed over thousands of cores. Two open-source packages are released along with this paper: Parallel Sweeping Preconditioner (PSP) and the underlying distributed multifrontal solver, Clique. © 2013 Society for Industrial and Applied Mathematics.

AB - A parallelization of a sweeping preconditioner for three-dimensional Helmholtz equations without large cavities is introduced and benchmarked for several challenging velocity models. The setup and application costs of the sequential preconditioner are shown to be O(γ2N4/3) and O(γN logN), where γ(ω) denotes the modestly frequency-dependent number of grid points per perfectly matched layer. Several computational and memory improvements are introduced relative to using black-box sparse-direct solvers for the auxiliary problems, and competitive runtimes and iteration counts are reported for high-frequency problems distributed over thousands of cores. Two open-source packages are released along with this paper: Parallel Sweeping Preconditioner (PSP) and the underlying distributed multifrontal solver, Clique. © 2013 Society for Industrial and Applied Mathematics.

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

UR - http://epubs.siam.org/doi/10.1137/120871985

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

U2 - 10.1137/120871985

DO - 10.1137/120871985

M3 - Article

SN - 1064-8275

VL - 35

SP - C194-C212

JO - SIAM Journal on Scientific Computing

JF - SIAM Journal on Scientific Computing

IS - 3

ER -

A Parallel Sweeping Preconditioner for Heterogeneous 3D Helmholtz Equations

Abstract

Access to Document

Other files and links

Fingerprint

Cite this