Wavelet Galerkin Algorithms for Boundary Integral Equations

The implementation of a fast, wavelet-based Galerkin discretization of second kind integral equations on piecewise smooth surfaces $\Gamma\subset \IR^3$ is described. It allows meshes consisting of triangles as well as quadrilaterals. The algorithm generates a sparse, approximate stiffness matrix with $\cN=O(N(\log N)^2)$ nonvanishing entries in O(N(log N)4) operations, where N is the number of degrees of freedom on the boundary, while essentially retaining the asymptotic convergence rate of the full Galerkin scheme. A new proof of the matrix-compression estimates is given based on derivative-free kernel estimates. The condition number of the sparse stiffness matrices is bounded independently of the meshwidth. The data structure containing the compressed stiffness matrix is described in detail: it requires $O(\cN)$ memory and can be set up in $O(\cN)$ operations. Numerical experiments show that the asymptotic performance estimates apply for moderate N. Problems with N=106 degrees of freedom were computed in core on a workstation. The impact of various parameters in the compression scheme on the performance and the accuracy of the algorithm is studied.