Report 1997-15

Wavelet Galerkin Algorithms for Boundary Integral Equations

C. Lage and C. Schwab

Abstract: 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=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.

Paper: Available as PDF (19 MB) or as hardcopy to order reports@sam.math.ethz.ch.