Wavelet Galerkin Algorithms for Boundary Integral Equations

Abstract

The implementation of a fast, wavelet-based Galerkin discretization of second kind integral equations on piecewise smooth surfaces $\Gamma\subset \R^3$ is described. It allows meshes consisting of triangles as well as quadrilaterals. The algorithm generates a sparse, approximate stiffness matrix with $N=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(N)$ memory and can be set up in $O(N)$ operations. Numerical experiments show that the asymptotic performance estimates apply for moderate N. Problems with $N=10^5$ 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.