The fast multipole method for integral equations of seismic scattering problems

A number of seismic scattering problems can be described by using boundary integral equations. Numerical methods to solve these equations replace integral equations by linear systems. These linear systems are usually non-symmetric and full, which often prohibits the computation of problems with a large size. To overcome this difficulty, a combination of the fast multipole method and an iterative method for non-symmetric linear systems is applied to seismic scattering problems and the applicability of the method is investigated. The fast multipole method reduces the order of operations for the product of the matrix obtained from the discretization of the integral kernel and a vector from N² operations to the order of p²N log N operations, where p is the order of the multipole expansion; memory requirements are also reduced. Although the number of iterations depends on the properties of the integral equation, for numerically stable problems described by a Fredholm integral equation of the second kind the combination of the fast multipole method and the iterative methods reduces the computation and memory requirements by 1 or 2 orders of magnitude for a problem with more than 10 000 unknown variables.