A log-linear time algorithm for the elastodynamic boundary integral equation method

Abstract

We present a fast and memory-efficient algorithm for transient, space-time-domain, and elastodynamic boundary-integral analysis. Associated data-sparse approximations and operations are named fast domain partitioning hierarchical matrices (FDP=H-matrices). The fast domain partitioning method (the FDPM) solves a known problem of hierarchical matrices (H-matrices) in compressing discretized elastodynamic kernel functions. A novel set of plane-wave approximations then unites the FDPM and H-matrices in an accurate analytic manner. Memory usage is $\mathcal{O}(N\log N)$ and computation time $\mathcal{O}(NM\log N)$ in our algorithm throughout one run with $N$ boundary elements and $M$ time steps. The amount of associated cost reduction is remarkable, as the memory usage and computational time have been originally $\mathcal{O}(N^{2}M)$ and $\mathcal{O}(N^2{M}^2)$, respectively, to run the orthodox time-marching implementation. Numerical experiments indicate that FDP=H-matrices achieve $\mathcal{O}(NM/\log N)$ times smaller memory and computation time while ensuring the accuracy of the analyses.

149 pages, 29 figures