Darve, Eric The fast multipole method. I: Error analysis and asymptotic complexity. (English) Zbl 0974.65033 SIAM J. Numer. Anal. 38, No. 1, 98-128 (2000). 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. Reviewer: Gisbert Stoyan (Budapest) Cited in 59 Documents 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 Keywords:scattering problems; multipole method; asymptotic complexity; convergence Citations:Zbl 0854.65122 PDFBibTeX XMLCite \textit{E. Darve}, SIAM J. Numer. Anal. 38, No. 1, 98--128 (2000; Zbl 0974.65033) Full Text: DOI