A fast, high-order algorithm for the solution of surface scattering problems: Basic implementation, tests, and applications

We present a new algorithm for the numerical solution of problems of acoust ic scattering by surfaces in three-dimensional space. This algorithm evalua tes scattered fields through fast, high-order solution of the corresponding boundary integral equation. The high-order accuracy of our solver is achie ved through use of partitions of unity together with analytical resolution of kernel singularities. The acceleration, in turn, results from use of a n ovel approach which, based on high-order "two-face" equivalent source appro ximations, reduces the evaluation of far interactions to evaluation of 3-D fast Fourier transforms (FFTs), This approach is faster and substantially m ore accurate, and it runs on dramatically smaller memories than other FFT a nd k-space methods. The present algorithm computes one matrix-vector multip lication in O(N-6/5 log N) to O(N-4/3 log N) operations, where N is the num ber of surface discretization points. The latter estimate applies to smooth surfaces, for which our high-order algorithm provides accurate solutions w ith small values of N; the former, more favorable count is valid for highly complex surfaces requiring significant amounts of subwavelength sampling. Further, our approach exhibits super-algebraic convergence. it can be appli ed to smooth and nonsmooth scatterers, and it does not suffer from accuracy breakdowns of any kind. In this paper we introduce the main algorithmic co mponents in our approach, and we demonstrate its performance with a variety of numerical results. In particular, we show that the present algorithm ca n evaluate accurately in a personal computer scattering from bodies of acou stical sizes Of several hundreds. (C) 2001 Academic Press.