Rapid solution of first kind boundary integral equations in 3

Abstract Weakly singular boundary integral equations (BIEs) of the first kind on polyhedral surfaces Γ in R 3 are discretized by Galerkin BEM on shape-regular, but otherwise unstructured meshes of meshwidth h . Strong ellipticity of the integral operator is shown to give nonsingular stiffness matrices and, for piecewise constant approximations, up to O( h 3 ) convergence of the farfield. The condition number of the stiffness matrix behaves like O( h −1 ) in the standard basis. An O( N ) agglomeration algorithm for the construction of a multilevel wavelet basis on Γ is introduced resulting in a preconditioner which reduces the condition number to O (| log h|). A class of kernel-independent clustering algorithms (containing the fast multipole method as special case) is introduced for approximate matrix–vector multiplication in O (N( log N) 3 ) memory and operations. Iterative approximate solution of the linear system by CG or GMRES with wavelet preconditioning and clustering-acceleration of matrix–vector multiplication is shown to yield an approximate solution in log-linear complexity which preserves the O( h 3 ) convergence of the potentials. Numerical experiments are given which confirm the theory.