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.
To the best of our knowledge, the most successful method for the Helmholtz kernel @math -body problem in both 2 and 3D is the high-frequency fast multipole method (HF-FMM) proposed by Rokhlin and his collaborators in a series of papers @cite_4 @cite_18 @cite_28 . This approach combines the analytic property of the Helmholtz kernel with an FFT-type fast algorithm to speedup the computation of the interaction between well-separated regions. If @math is the number of input and output points as before, the resulting algorithm has an @math computational complexity. Other algorithms using similar techniques can be found in @cite_21 @cite_34 @cite_38 @cite_0 .
@cite_38 @cite_18 @cite_4 @cite_28 @cite_21 @cite_0 @cite_34
1621423264 1963750172 1968359830 2117762537
This paper introduces a directional multiscale algorithm for the two dimensional @math -body problem of the Helmholtz kernel with applications to high frequency scattering. The algorithm follows the approach in [Engquist and Ying, SIAM Journal on Scientific Computing, 29 (4), 2007] where the three dimensional case was studied. The main observation is that, for two regions that follow a directional parabolic geometric configuration, the interaction between the points in these two regions through the Helmholtz kernel is approximately low rank. We propose an improved randomized procedure for generating the low rank representations. Based on these representations, we organize the computation of the far field interaction in a multidirectional and multiscale way to achieve maximum efficiency. The proposed algorithm is accurate and has the optimal @math complexity for problems from two dimensional scattering applications. We present numerical results for several test examples to illustrate the algorithm and its application to two dimensional high frequency scattering problems. We describe a wideband version of the Fast Multipole Method for the Helmholtz equation in three dimensions. It unifies previously existing versions of the FMM for high and low frequencies into an algorithm which is accurate and efficient for any frequency, having a CPU time of O(N) if low-frequency computations dominate, or O(NlogN) if high-frequency computations dominate. The performance of the algorithm is illustrated with numerical examples. The solution of Helmholtz and Maxwell equations by integral formulations (kernel in exp( i kr) r ) leads to large dense linear systems. Using direct solvers requires large computational costs in O(N 3 ) . Using iterative solvers, the computational cost is reduced to large matrix–vector products. The fast multipole method provides a fast numerical way to compute convolution integrals. Its application to Maxwell and Helmholtz equations was initiated by Rokhlin, based on a multipole expansion of the interaction kernel. A second version, proposed by Chew, is based on a plane–wave expansion of the kernel. We propose a third approach, the stable–plane–wave expansion, which has a lower computational expense than the multipole expansion and does not have the accuracy and stability problems of the plane–wave expansion. The computational complexity is N log N as with the other methods. This paper introduces a new directional multilevel algorithm for solving @math -body or @math -point problems with highly oscillatory kernels. These systems often result from the boundary integral formulations of scattering problems and are difficult due to the oscillatory nature of the kernel and the non-uniformity of the particle distribution. We address the problem by first proving that the interaction between a ball of radius @math and a well-separated region has an approximate low rank representation, as long as the well-separated region belongs to a cone with a spanning angle of @math and is at a distance which is at least @math away from from the ball. We then propose an efficient and accurate procedure which utilizes random sampling to generate such a separated, low rank representation. Based on the resulting representations, our new algorithm organizes the high frequency far field computation by a multidirectional and multiscale strategy to achieve maximum efficiency. The algorithm performs well on a large group of highly oscillatory kernels. Our algorithm is proved to have @math computational complexity for any given accuracy when the points are sampled from a two dimensional surface. We also provide numerical results to demonstrate these properties.