Fast convolution quadrature for the wave equation in three dimensions

L. Banjai, M. Kachanovska

Research output: Contribution to journalArticle

Abstract

This work addresses the numerical solution of time-domain boundary integral equations arising from acoustic and electromagnetic scattering in three dimensions. The semidiscretization of the time-domain boundary integral equations by Runge-Kutta convolution quadrature leads to a lower triangular Toeplitz system of size N. This system can be solved recursively in an almost linear time (O(Nlog2N)), but requires the construction of O(N) dense spatial discretizations of the single layer boundary operator for the Helmholtz equation. This work introduces an improvement of this algorithm that allows to solve the scattering problem in an almost linear time. The new approach is based on two main ingredients: the near-field reuse and the application of data-sparse techniques. Exponential decay of Runge-Kutta convolution weights wnh(d) outside of a neighborhood of d≈. nh (where h is a time step) allows to avoid constructing the near-field (i.e. singular and near-singular integrals) for most of the discretizations of the single layer boundary operators (near-field reuse). The far-field of these matrices is compressed with the help of data-sparse techniques, namely, H-matrices and the high-frequency fast multipole method. Numerical experiments indicate the efficiency of the proposed approach compared to the conventional Runge-Kutta convolution quadrature algorithm.

Original languageEnglish
Pages (from-to)103-126
Number of pages24
JournalJournal of Computational Physics
Volume279
DOIs
Publication statusPublished - 2014

Fingerprint

Wave equations
Convolution
Boundary integral equations
Boundary layers
Scattering
Helmholtz equation
Acoustics
Experiments

Keywords

  • Boundary element method
  • Fast multipole method
  • H-matrices
  • Runge-Kutta convolution quadrature
  • Time-domain boundary integral equations
  • Wave scattering

Cite this

@article{e1d865c6234045c19d8e3904acad3c1c,
title = "Fast convolution quadrature for the wave equation in three dimensions",
abstract = "This work addresses the numerical solution of time-domain boundary integral equations arising from acoustic and electromagnetic scattering in three dimensions. The semidiscretization of the time-domain boundary integral equations by Runge-Kutta convolution quadrature leads to a lower triangular Toeplitz system of size N. This system can be solved recursively in an almost linear time (O(Nlog2N)), but requires the construction of O(N) dense spatial discretizations of the single layer boundary operator for the Helmholtz equation. This work introduces an improvement of this algorithm that allows to solve the scattering problem in an almost linear time. The new approach is based on two main ingredients: the near-field reuse and the application of data-sparse techniques. Exponential decay of Runge-Kutta convolution weights wnh(d) outside of a neighborhood of d≈. nh (where h is a time step) allows to avoid constructing the near-field (i.e. singular and near-singular integrals) for most of the discretizations of the single layer boundary operators (near-field reuse). The far-field of these matrices is compressed with the help of data-sparse techniques, namely, H-matrices and the high-frequency fast multipole method. Numerical experiments indicate the efficiency of the proposed approach compared to the conventional Runge-Kutta convolution quadrature algorithm.",
keywords = "Boundary element method, Fast multipole method, H-matrices, Runge-Kutta convolution quadrature, Time-domain boundary integral equations, Wave scattering",
author = "L. Banjai and M. Kachanovska",
year = "2014",
doi = "10.1016/j.jcp.2014.08.049",
language = "English",
volume = "279",
pages = "103--126",
journal = "Journal of Computational Physics",
issn = "0021-9991",
publisher = "Academic Press Inc.",

}

Fast convolution quadrature for the wave equation in three dimensions. / Banjai, L.; Kachanovska, M.

In: Journal of Computational Physics, Vol. 279, 2014, p. 103-126.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Fast convolution quadrature for the wave equation in three dimensions

AU - Banjai, L.

AU - Kachanovska, M.

PY - 2014

Y1 - 2014

N2 - This work addresses the numerical solution of time-domain boundary integral equations arising from acoustic and electromagnetic scattering in three dimensions. The semidiscretization of the time-domain boundary integral equations by Runge-Kutta convolution quadrature leads to a lower triangular Toeplitz system of size N. This system can be solved recursively in an almost linear time (O(Nlog2N)), but requires the construction of O(N) dense spatial discretizations of the single layer boundary operator for the Helmholtz equation. This work introduces an improvement of this algorithm that allows to solve the scattering problem in an almost linear time. The new approach is based on two main ingredients: the near-field reuse and the application of data-sparse techniques. Exponential decay of Runge-Kutta convolution weights wnh(d) outside of a neighborhood of d≈. nh (where h is a time step) allows to avoid constructing the near-field (i.e. singular and near-singular integrals) for most of the discretizations of the single layer boundary operators (near-field reuse). The far-field of these matrices is compressed with the help of data-sparse techniques, namely, H-matrices and the high-frequency fast multipole method. Numerical experiments indicate the efficiency of the proposed approach compared to the conventional Runge-Kutta convolution quadrature algorithm.

AB - This work addresses the numerical solution of time-domain boundary integral equations arising from acoustic and electromagnetic scattering in three dimensions. The semidiscretization of the time-domain boundary integral equations by Runge-Kutta convolution quadrature leads to a lower triangular Toeplitz system of size N. This system can be solved recursively in an almost linear time (O(Nlog2N)), but requires the construction of O(N) dense spatial discretizations of the single layer boundary operator for the Helmholtz equation. This work introduces an improvement of this algorithm that allows to solve the scattering problem in an almost linear time. The new approach is based on two main ingredients: the near-field reuse and the application of data-sparse techniques. Exponential decay of Runge-Kutta convolution weights wnh(d) outside of a neighborhood of d≈. nh (where h is a time step) allows to avoid constructing the near-field (i.e. singular and near-singular integrals) for most of the discretizations of the single layer boundary operators (near-field reuse). The far-field of these matrices is compressed with the help of data-sparse techniques, namely, H-matrices and the high-frequency fast multipole method. Numerical experiments indicate the efficiency of the proposed approach compared to the conventional Runge-Kutta convolution quadrature algorithm.

KW - Boundary element method

KW - Fast multipole method

KW - H-matrices

KW - Runge-Kutta convolution quadrature

KW - Time-domain boundary integral equations

KW - Wave scattering

U2 - 10.1016/j.jcp.2014.08.049

DO - 10.1016/j.jcp.2014.08.049

M3 - Article

VL - 279

SP - 103

EP - 126

JO - Journal of Computational Physics

JF - Journal of Computational Physics

SN - 0021-9991

ER -