×

The fast multipole method. I: Error analysis and asymptotic complexity. (English) Zbl 0974.65033

For the computation of scattering problems on perfectly conducting objects, an integral equation for the currents on the scattering surface can be formulated and leads (using a Galerkin approach) to a large linear system with dense matrix. The author studies the so-called fast multipole method for the iterative solution of this linear system. The estimation of the asymptotic complexity – the amount of arithmetical operations (\(O(n\log^2n)\)) and memory required (\(O(n\log n)\)) – is proved. This proof bases on an investigation of the convergence of Geigenbauer series which results in a sharp criterion for the truncation of these series for a given accuracy, improving an earlier result of J. Rahola [BIT 36, No. 2, 333-358 (1996; Zbl 0854.65122)].
The author also reports shortly on the implementation of his method for a large practical problem.

MSC:

65F10 Iterative numerical methods for linear systems
65Y20 Complexity and performance of numerical algorithms
78M15 Boundary element methods applied to problems in optics and electromagnetic theory
78A45 Diffraction, scattering
65N38 Boundary element methods for boundary value problems involving PDEs
35Q60 PDEs in connection with optics and electromagnetic theory

Citations:

Zbl 0854.65122
PDFBibTeX XMLCite
Full Text: DOI