An O(1) integration scheme for three-dimensional surface scattering problems

We present an accurate method of O(1)-complexity with respect to frequency (i.e., a method that, to achieve a prescribed error tolerance, requires a bounded computational cost for arbitrarily high frequencies) for the computation of singular oscillatory integrals arising in the boundary integral formulation of problems of acoustic scattering by surfaces in three-dimensional space. Like the two-dimensional counterpart of this algorithm, which we introduced recently and which is applicable to scattering by curves in the plane, the present method is based on a combination of two main elements: (1) a high-frequency ansatz for the unknown density in a boundary integral formulation of the problem, and (2) an extension of the ideas of the method of stationary phase to allow for O(1) (high-order-accurate) integration of oscillatory functions. The techniques we introduce to implement an efficient O(1) integrator in the present three-dimensional context differ significantly from those used in the earlier two-dimensional algorithm. In particular, in the present text, we introduce an efficient “canonical” (hybrid analytic-numerical) algorithm which, in addition to allowing for integration of oscillatory functions around both singular points and points of stationary phase, can handle the significant difficulty that arises as singular points and one or more stationary points approach each other within the two-dimensional scattering surface. We include numerical results illustrating the behavior of the integration algorithm on sound-soft spheres with diameters of up to 5000 wavelengths: in such cases, for a single integral, the algorithm yields accuracies of the order of three digits in computational times of less than two seconds. In a preliminary full scattering simulation we present, a solution with two digits of accuracy in the surface density was obtained in about three hours running time, in a single 1.5 GHz AMD Athlon processor, for a sphere of 500 wavelengths in diameter