A fast algorithm for Quadrature by Expansion in three dimensions

Research output: Contribution to journalArticle

Abstract

This paper presents an accelerated quadrature scheme for the evaluation of layer potentials in three dimensions. Our scheme combines a generic, high order quadrature method for singular kernels called Quadrature by Expansion (QBX) with a modified version of the Fast Multipole Method (FMM). Our scheme extends a recently developed formulation of the FMM for QBX in two dimensions, which, in that setting, achieves mathematically rigorous error and running time bounds. In addition to generalization to three dimensions, we highlight some algorithmic and mathematical opportunities for improved performance and stability. Lastly, we give numerical evidence supporting the accuracy, performance, and scalability of the algorithm through a series of experiments involving the Laplace and Helmholtz equations.

Original languageEnglish (US)
Pages (from-to)655-689
Number of pages35
JournalJournal of Computational Physics
Volume388
DOIs
StatePublished - Jul 1 2019

Fingerprint

quadratures
Helmholtz equation
expansion
Laplace equation
multipoles
Scalability
Helmholtz equations
Experiments
formulations
evaluation

Keywords

  • Fast algorithms
  • Fast multipole method
  • Integral equations
  • Quadrature
  • Singular integrals
  • Three dimensional problems

ASJC Scopus subject areas

  • Numerical Analysis
  • Modeling and Simulation
  • Physics and Astronomy (miscellaneous)
  • Physics and Astronomy(all)
  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics

Cite this

A fast algorithm for Quadrature by Expansion in three dimensions. / Wala, Matt; Kloeckner, Andreas Paul Eberhard.

In: Journal of Computational Physics, Vol. 388, 01.07.2019, p. 655-689.

Research output: Contribution to journalArticle

@article{d3ef184084b0469cb6546fa53fdc4334,
title = "A fast algorithm for Quadrature by Expansion in three dimensions",
abstract = "This paper presents an accelerated quadrature scheme for the evaluation of layer potentials in three dimensions. Our scheme combines a generic, high order quadrature method for singular kernels called Quadrature by Expansion (QBX) with a modified version of the Fast Multipole Method (FMM). Our scheme extends a recently developed formulation of the FMM for QBX in two dimensions, which, in that setting, achieves mathematically rigorous error and running time bounds. In addition to generalization to three dimensions, we highlight some algorithmic and mathematical opportunities for improved performance and stability. Lastly, we give numerical evidence supporting the accuracy, performance, and scalability of the algorithm through a series of experiments involving the Laplace and Helmholtz equations.",
keywords = "Fast algorithms, Fast multipole method, Integral equations, Quadrature, Singular integrals, Three dimensional problems",
author = "Matt Wala and Kloeckner, {Andreas Paul Eberhard}",
year = "2019",
month = "7",
day = "1",
doi = "10.1016/j.jcp.2019.03.024",
language = "English (US)",
volume = "388",
pages = "655--689",
journal = "Journal of Computational Physics",
issn = "0021-9991",
publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - A fast algorithm for Quadrature by Expansion in three dimensions

AU - Wala, Matt

AU - Kloeckner, Andreas Paul Eberhard

PY - 2019/7/1

Y1 - 2019/7/1

N2 - This paper presents an accelerated quadrature scheme for the evaluation of layer potentials in three dimensions. Our scheme combines a generic, high order quadrature method for singular kernels called Quadrature by Expansion (QBX) with a modified version of the Fast Multipole Method (FMM). Our scheme extends a recently developed formulation of the FMM for QBX in two dimensions, which, in that setting, achieves mathematically rigorous error and running time bounds. In addition to generalization to three dimensions, we highlight some algorithmic and mathematical opportunities for improved performance and stability. Lastly, we give numerical evidence supporting the accuracy, performance, and scalability of the algorithm through a series of experiments involving the Laplace and Helmholtz equations.

AB - This paper presents an accelerated quadrature scheme for the evaluation of layer potentials in three dimensions. Our scheme combines a generic, high order quadrature method for singular kernels called Quadrature by Expansion (QBX) with a modified version of the Fast Multipole Method (FMM). Our scheme extends a recently developed formulation of the FMM for QBX in two dimensions, which, in that setting, achieves mathematically rigorous error and running time bounds. In addition to generalization to three dimensions, we highlight some algorithmic and mathematical opportunities for improved performance and stability. Lastly, we give numerical evidence supporting the accuracy, performance, and scalability of the algorithm through a series of experiments involving the Laplace and Helmholtz equations.

KW - Fast algorithms

KW - Fast multipole method

KW - Integral equations

KW - Quadrature

KW - Singular integrals

KW - Three dimensional problems

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

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

U2 - 10.1016/j.jcp.2019.03.024

DO - 10.1016/j.jcp.2019.03.024

M3 - Article

VL - 388

SP - 655

EP - 689

JO - Journal of Computational Physics

JF - Journal of Computational Physics

SN - 0021-9991

ER -