This paper is concerned with the fast computation of Fourier integral operators of the general form @math , where @math is a frequency variable, @math is a phase function obeying a standard homogeneity condition, and @math is a given input. This is of interest for such fundamental computations are connected with the problem of finding numerical solutions to wave equations, and also frequently arise in many applications including reflection seismology, curvilinear tomography and others. In two dimensions, when the input and output are sampled on @math Cartesian grids, a direct evaluation requires @math operations, which is often times prohibitively expensive. This paper introduces a novel algorithm running in @math time, i. e. with near-optimal computational complexity, and whose overall structure follows that of the butterfly algorithm [Michielssen and Boag, IEEE Trans Antennas Propagat 44 (1996), 1086-1093]. Underlying this algorithm is a mathematical insight concerning the restriction of the kernel @math to subsets of the time and frequency domains. Whenever these subsets obey a simple geometric condition, the restricted kernel has approximately low-rank; we propose constructing such low-rank approximations using a special interpolation scheme, which prefactors the oscillatory component, interpolates the remaining nonoscillatory part and, lastly, remodulates the outcome. A byproduct of this scheme is that the whole algorithm is highly efficient in terms of memory requirement. Numerical results demonstrate the performance and illustrate the empirical properties of this algorithm.
In a different direction, there has been a great amount of research on other types of oscillatory integral transforms. An important example is the discrete @math -body problem where one wants to evaluate sums of the form [ 1 j n q_j K(|x-x_j|), K(r) = e^ r r ] in the high-frequency regime ( @math is large). Such problems appear naturally when solving the Helmholtz equation by means of a boundary integral formulation @cite_1 @cite_17 . A popular approach seeks to compress the oscillatory integral operator by representing it in an appropriate basis such as a local Fourier basis, or a basis extracted from the wavelet packet dictionary @cite_36 @cite_12 @cite_13 @cite_25 . This representation sparsifies the operator, thus allowing fast matrix-vector products. In spite of having good theoretical estimates, this approach has thus far been practically limited to 1D boundaries. One particular issue with this approach is that the evaluation of the remaining nonnegligible coefficients sometimes requires assembling the entire matrix, which can be computationally rather expensive.
@cite_36 @cite_1 @cite_13 @cite_25 @cite_12 @cite_17
1969569206 2096240124 1993700748 1517670975
Abstract The integral ∫0Leiνφ(s,t)f(s)dswith a highly oscillatory kernel (large ν, ν is up to 2000) is considered. This integral is accurately evaluated with an improved trapezoidal rule and effectively transcribed using local Fourier basis and adaptive multiscale local Fourier basis. The representation of the oscillatory kernel in these bases is sparse. The coefficients after the application of local Fourier transform are smoothed. Sometimes this enables us to obtain further compression with wavelets. We examine the use of wavelet packets for the fast solution of integral equations with a highly oscillatory kernel. The redundancy of the wavelet packet transform allows the selection of a basis tailored to the problem at hand. It is shown that a well chosen wavelet packet basis is better suited to compress the discretized system than wavelets. The complexity of the matrix-vector product in an iterative solution method is then substantially reduced. A two-dimensional wavelet packet transform is derived and compared with a number of one-dimensional transforms that were presented earlier in literature. By means of some numerical experiments we illustrate the improved efficiency of the two-dimensional approach. Abstract We prove that certain oscillatory boundary integral operators occurring in acoustic scattering computations become sparse when represented in the appropriate local cosine transform orthonormal basis. Preface to the Classics Edition Preface Symbols 1. The Riesz-Fredholm theory for compact operators 2. Regularity properties of surface potentials 3. Boundary-value problems for the scalar Helmholtz equation 4. Boundary-value problems for the time-harmonic Maxwell equations and the vector Helmholtz equation 5. Low frequency behavior of solutions to boundary-value problems in scattering theory 6. The inverse scattering problem: exact data 7. Improperly posed problems and compact families 8. The determination of the shape of an obstacle from inexact far-field data 9. Optimal control problems in radiation and scattering theory References Index.