Rapid solution of first kind boundary integral equations in $R^3$

Abstract

Weakly singular boundary integral equations $(BIEs)$ of the first kind on polyhedral surfaces $\Gamma$ in $R^3$ are discretized by Galerkin $BEM$ on shape-regular, but otherwise unstructured meshes of mesh width $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 $\Gamma$ 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.