Fourier-Based Fast Multipole Method for the Helmholtz Equation

Cris Cecka; Eric Darve

doi:10.1137/11085774X

Fourier-Based Fast Multipole Method for the Helmholtz Equation

Cris Cecka, Eric Darve

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

24 Scopus citations

Abstract

The fast multipole method (FMM) has had great success in reducing the computational complexity of solving the boundary integral form of the Helmholtz equation. We present a formulation of the Helmholtz FMM that uses Fourier basis functions rather than spherical harmonics. By modifying the transfer function in the precomputation stage of the FMM, time-critical stages of the algorithm are accelerated by causing the interpolation operators to become straightforward applications of fast Fourier transforms, retaining the diagonality of the transfer function, and providing a simplified error analysis. Using Fourier analysis, constructive algorithms are derived to a priori determine an integration quadrature for a given error tolerance. Sharp error bounds are derived and verified numerically. Various optimizations are considered to reduce the number of quadrature points and reduce the cost of computing the transfer function. © 2013 Society for Industrial and Applied Mathematics.

Original language	English (US)
Pages (from-to)	A79-A103
Number of pages	1
Journal	SIAM Journal on Scientific Computing
Volume	35
Issue number	1
DOIs	https://doi.org/10.1137/11085774X
State	Published - Jan 2013
Externally published	Yes

Access to Document

10.1137/11085774X

Cite this

@article{ac7730bd46d148b7b92e61be6373aa06,

title = "Fourier-Based Fast Multipole Method for the Helmholtz Equation",

abstract = "The fast multipole method (FMM) has had great success in reducing the computational complexity of solving the boundary integral form of the Helmholtz equation. We present a formulation of the Helmholtz FMM that uses Fourier basis functions rather than spherical harmonics. By modifying the transfer function in the precomputation stage of the FMM, time-critical stages of the algorithm are accelerated by causing the interpolation operators to become straightforward applications of fast Fourier transforms, retaining the diagonality of the transfer function, and providing a simplified error analysis. Using Fourier analysis, constructive algorithms are derived to a priori determine an integration quadrature for a given error tolerance. Sharp error bounds are derived and verified numerically. Various optimizations are considered to reduce the number of quadrature points and reduce the cost of computing the transfer function. {\textcopyright} 2013 Society for Industrial and Applied Mathematics.",

author = "Cris Cecka and Eric Darve",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: This research was supported by the U.S. Army Research Laboratory, through the Army HighPerformance Computing Research Center, Cooperative Agreement W911NF-07-0027, the StanfordSchool of Engineering, and the King Abdullah University of Science and Technology. This publication acknowledges KAUST support, but has no KAUST affiliated authors.",

year = "2013",

month = jan,

doi = "10.1137/11085774X",

language = "English (US)",

volume = "35",

pages = "A79--A103",

journal = "SIAM Journal on Scientific Computing",

issn = "1064-8275",

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

number = "1",

}

TY - JOUR

T1 - Fourier-Based Fast Multipole Method for the Helmholtz Equation

AU - Cecka, Cris

AU - Darve, Eric

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: This research was supported by the U.S. Army Research Laboratory, through the Army HighPerformance Computing Research Center, Cooperative Agreement W911NF-07-0027, the StanfordSchool of Engineering, and the King Abdullah University of Science and Technology. This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2013/1

Y1 - 2013/1

N2 - The fast multipole method (FMM) has had great success in reducing the computational complexity of solving the boundary integral form of the Helmholtz equation. We present a formulation of the Helmholtz FMM that uses Fourier basis functions rather than spherical harmonics. By modifying the transfer function in the precomputation stage of the FMM, time-critical stages of the algorithm are accelerated by causing the interpolation operators to become straightforward applications of fast Fourier transforms, retaining the diagonality of the transfer function, and providing a simplified error analysis. Using Fourier analysis, constructive algorithms are derived to a priori determine an integration quadrature for a given error tolerance. Sharp error bounds are derived and verified numerically. Various optimizations are considered to reduce the number of quadrature points and reduce the cost of computing the transfer function. © 2013 Society for Industrial and Applied Mathematics.

AB - The fast multipole method (FMM) has had great success in reducing the computational complexity of solving the boundary integral form of the Helmholtz equation. We present a formulation of the Helmholtz FMM that uses Fourier basis functions rather than spherical harmonics. By modifying the transfer function in the precomputation stage of the FMM, time-critical stages of the algorithm are accelerated by causing the interpolation operators to become straightforward applications of fast Fourier transforms, retaining the diagonality of the transfer function, and providing a simplified error analysis. Using Fourier analysis, constructive algorithms are derived to a priori determine an integration quadrature for a given error tolerance. Sharp error bounds are derived and verified numerically. Various optimizations are considered to reduce the number of quadrature points and reduce the cost of computing the transfer function. © 2013 Society for Industrial and Applied Mathematics.

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

UR - http://epubs.siam.org/doi/10.1137/11085774X

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

U2 - 10.1137/11085774X

DO - 10.1137/11085774X

M3 - Article

SN - 1064-8275

VL - 35

SP - A79-A103

JO - SIAM Journal on Scientific Computing

JF - SIAM Journal on Scientific Computing

IS - 1

ER -

Fourier-Based Fast Multipole Method for the Helmholtz Equation

Abstract

Access to Document

Other files and links

Fingerprint

Cite this