Fast and scalable solvers for the Helmholtz equation

In this thesis we develop a new family of fast and scalable algorithms to solve the 2D high-frequency Helmholtz equation in heterogeneous medium. The algorithms rely on a layered domain decomposition and a coupling between subdomains using the Green's representation formula, which reduces the problem to a boundary integral system at the interfaces between subdomains. Simultaneously, we introduce a polarization of the waves in up- and down-going components using incomplete Green's integrals, which induces another equivalent boundary integral formulation that is easy to precondition. The computation is divided in two stages: an offline stage, a computationally expensive but embarrassingly parallel precomputation performed only once; and an online stage, a highly parallel computation with low complexity performed for each right-hand side. The computational efficiency of the algorithms is achieved by shifting most of the computational burden to an offline precomputation, and by reducing the sequential bottleneck in the online stage using an efficient preconditioner, based on the polarized decomposition, coupled with compressed linear algebra. The resulting algorithms have online runtime O(N/P), where N is the number of unknowns, and P is the number of nodes in a distributed memory environment; provided that P = O (N [alpha]). Typically [alpha] = 1/5 or 1/8.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Mathematics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Zepeda-Núñ̃ez, Leonardo Andrés

Advisor dc:contributor.advisor

• Laurent Demanet.

• Mathematics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/99061

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/99061