### 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(Nlog^{2}N)), 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 language | English |
---|---|

Pages (from-to) | 103-126 |

Number of pages | 24 |

Journal | Journal of Computational Physics |

Volume | 279 |

DOIs | |

Publication status | Published - 2014 |

### Fingerprint

### Keywords

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

### Cite this

*Journal of Computational Physics*,

*279*, 103-126. https://doi.org/10.1016/j.jcp.2014.08.049

}

*Journal of Computational Physics*, vol. 279, pp. 103-126. https://doi.org/10.1016/j.jcp.2014.08.049

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

Research output: Contribution to journal › Article

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 -