An interpolation-based fast-multipole accelerated boundary integral equation method for the three-dimensional wave equation

A new fast multipole method (FMM) is proposed to accelerate the time-domain boundary integral equation method (TDBIEM) for the three-dimensional wave equation. The proposed algorithm is an enhancement of the interpolation-based FMM for the time-domain case, adopting the notion of the plane-wave time-domain algorithm. With the application being targeted at a low-frequency regime, the proposed time-domain interpolation-based FMM can reduce the computational complexity of the TDBIEM from O((NsNt)-N-2) to O(N-s(1+delta) N-t) (where delta = 1/3 or 1/2) with the help of multilevel space-time hierarchy, where N-s and N-t are the spatial and temporal degrees of freedom, respectively. The computational accuracy and speed of the proposed accelerated TDBIEM are verified in comparison with those of the conventional (direct) TDBIEM via numerical experiments. (C) 2013 Elsevier Inc. All rights reserved.