Fast evaluation of three-dimensional transient wave fields using diagonal translation operators

This paper presents novel plane wave time domain (PWTD) algorithms which accelerate the computational analysis of transient surface scattering phenomena. The proposed PWTD algorithms permit the fast evaluation of transient fields satisfying the wave equation. The cost associated with the computation of fields at N-s observers produced by a surface bound source density represented in terms of N-s spatial samples for N-t time steps scales as O (NtNS2) if classical time domain integral-equation-based methods are used. It is shown that this cost can be reduced to O(NtNs4/3 log N-s) and O(NtNs log N-s) using two-level and multilevel PWTD schemes, respectively. These algorithms are the time domain counterparts of frequency domain fast multipole methods and make feasible the practical broadband analysis of scattering from large and complexbodies. (C) 1998 Academic Press.