L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation
© 2020 Elsevier Inc. We present the first fast solver for the high-frequency Helmholtz equation that scales optimally in parallel for a single right-hand side. The L-sweeps approach achieves this scalability by departing from the usual propagation pattern, in which information flows in a 180∘ degree...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Elsevier BV
2021
|
| Online Access: | https://hdl.handle.net/1721.1/136075 |
| _version_ | 1811090385906171904 |
|---|---|
| author | Taus, Matthias Zepeda-Núñez, Leonardo Hewett, Russell J Demanet, Laurent |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Taus, Matthias Zepeda-Núñez, Leonardo Hewett, Russell J Demanet, Laurent |
| author_sort | Taus, Matthias |
| collection | MIT |
| description | © 2020 Elsevier Inc. We present the first fast solver for the high-frequency Helmholtz equation that scales optimally in parallel for a single right-hand side. The L-sweeps approach achieves this scalability by departing from the usual propagation pattern, in which information flows in a 180∘ degree cone from interfaces in a layered decomposition. Instead, with L-sweeps, information propagates in 90∘ cones induced by a Cartesian domain decomposition (CDD). We extend the notion of accurate transmission conditions to CDDs and introduce a new sweeping strategy to efficiently track the wave fronts as they propagate through the CDD. The new approach decouples the subdomains at each wave front, so that they can be processed in parallel, resulting in better parallel scalability than previously demonstrated in the literature. The method has an overall O((N/p)logω) empirical run-time for N=nd total degrees-of-freedom in a d-dimensional problem, frequency ω, and p=O(n) processors. We introduce the algorithm and provide a complexity analysis for our parallel implementation of the solver. We corroborate all claims in several two- and three-dimensional numerical examples involving constant, smooth, and discontinuous wave speeds. |
| first_indexed | 2024-09-23T14:44:46Z |
| format | Article |
| id | mit-1721.1/136075 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:44:46Z |
| publishDate | 2021 |
| publisher | Elsevier BV |
| record_format | dspace |
| spelling | mit-1721.1/1360752023-12-20T16:30:36Z L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation Taus, Matthias Zepeda-Núñez, Leonardo Hewett, Russell J Demanet, Laurent Massachusetts Institute of Technology. Department of Mathematics © 2020 Elsevier Inc. We present the first fast solver for the high-frequency Helmholtz equation that scales optimally in parallel for a single right-hand side. The L-sweeps approach achieves this scalability by departing from the usual propagation pattern, in which information flows in a 180∘ degree cone from interfaces in a layered decomposition. Instead, with L-sweeps, information propagates in 90∘ cones induced by a Cartesian domain decomposition (CDD). We extend the notion of accurate transmission conditions to CDDs and introduce a new sweeping strategy to efficiently track the wave fronts as they propagate through the CDD. The new approach decouples the subdomains at each wave front, so that they can be processed in parallel, resulting in better parallel scalability than previously demonstrated in the literature. The method has an overall O((N/p)logω) empirical run-time for N=nd total degrees-of-freedom in a d-dimensional problem, frequency ω, and p=O(n) processors. We introduce the algorithm and provide a complexity analysis for our parallel implementation of the solver. We corroborate all claims in several two- and three-dimensional numerical examples involving constant, smooth, and discontinuous wave speeds. 2021-10-27T20:30:41Z 2021-10-27T20:30:41Z 2020 2021-05-18T18:20:35Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/136075 en 10.1016/J.JCP.2020.109706 Journal of Computational Physics Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier BV arXiv |
| spellingShingle | Taus, Matthias Zepeda-Núñez, Leonardo Hewett, Russell J Demanet, Laurent L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation |
| title | L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation |
| title_full | L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation |
| title_fullStr | L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation |
| title_full_unstemmed | L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation |
| title_short | L-Sweeps: A scalable, parallel preconditioner for the high-frequency Helmholtz equation |
| title_sort | l sweeps a scalable parallel preconditioner for the high frequency helmholtz equation |
| url | https://hdl.handle.net/1721.1/136075 |
| work_keys_str_mv | AT tausmatthias lsweepsascalableparallelpreconditionerforthehighfrequencyhelmholtzequation AT zepedanunezleonardo lsweepsascalableparallelpreconditionerforthehighfrequencyhelmholtzequation AT hewettrussellj lsweepsascalableparallelpreconditionerforthehighfrequencyhelmholtzequation AT demanetlaurent lsweepsascalableparallelpreconditionerforthehighfrequencyhelmholtzequation |