Surface scattering in three dimensions: An accelerated high-order solver

We present a new algorithm for the numerical solution of problems of acoustic scattering by surfaces in three-dimensional space. This algorithm evaluates scattered fields through fast, high-order, accurate solution of the corresponding boundary integral equation. The high-order accuracy of our solver is achieved through use of partitions of unity together with analytical resolution of kernel singularities. The acceleration, in turn, results from use of high-order equivalent source approximations, which allow for fast evaluation of non-adjacent interactions by means of the three-dimensional fast Fourier transform (FFT). Our acceleration scheme has dramatically lower memory requirements and yields much higher accuracy than existing FFT-accelerated techniques. The present algorithm computes one matrix-vector multiply in O(N^6/5 log N) to O(N^4/3 log N) operations (depending on the geometric characteristics of the scattering surface), it exhibits super-algebraic convergence, and it does not suffer from accuracy breakdowns of any kind. We demonstrate the efficiency of our method through a variety of examples. In particular, we show that the present algorithm can evaluate accurately, on a personal computer, scattering from bodies of acoustical sizes (ka) of several hundreds.