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.
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. Abstract The diagonal forms are constructed for the translation operators for the Helmholtz equation in three dimensions. While the operators themselves have a fairly complicated structure (described somewhat incompletely by the classical addition theorems for the Bessel functions), their diagonal forms turn out to be quite simple. These diagonal forms are realized as generalized integrals, possess straightforward physical interpretations, and admit stable numerical implementation. This paper uses the obtained analytical apparatus to construct an algorithm for the rapid application to arbitrary vectors of matrices resulting from the discretization of integral equations of the potential theory for the Helmholtz equation in three dimensions. It is an extension to the three-dimensional case of the results of Rokhlin (J. Complexity4(1988), 12-32), where a similar apparatus is developed in the two-dimensional case. Abstract The present paper describes an algorithm for rapid solution of boundary value problems for the Helmholtz equation in two dimensions based on iteratively solving integral equations of scattering theory. CPU time requirements of previously published algorithms of this type are of the order n 2 , where n is the number of nodes in the discretization of the boundary of the scatterer. The CPU time requirements of the algorithm of the present paper are n 4 3 , and can be further reduced, making it considerably more practical for large scale 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 fast multipole method (FMM) has been implemented to speed up the matrix-vector multiply when an iterative method is used to solve the combined field integral equation (CFIE). FMM reduces the complexity from O(N2) to O(N1.5). With a multilevel fast multipole algorithm (MLFMA), it is further reduced to O(N log N). A 110, 592-unknown problem can be solved within 24 h on a SUN Sparc 10. © 1995 John Wiley & Sons, Inc. We study integral methods applied to the resolution of the Maxwell equations where the linear system is solved using an iterative method which requires only matrix?vector products. The fast multipole method (FMM) is one of the most efficient methods used to perform matrix?vector products and accelerate the resolution of the linear system. A problem involving N degrees of freedom may be solved in CNiterNlogN floating operations, where C is a constant depending on the implementation of the method. In this article several techniques allowing one to reduce the constant C are analyzed. This reduction implies a lower total CPU time and a larger range of application of the FMM. In particular, new interpolation and anterpolation schemes are proposed which greatly improve on previous algorithms. Several numerical tests are also described. These confirm the efficiency and the theoretical complexity of the FMM.