Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation
Title Fast methods for the numerical solution of boundray integral equations
Participant Klaus Giebermann
Key words Boundary integral equations, boundary element method, fast summation methods, panel clustering, fast multipole method
Description A wide range of interesting problems can be formulated as boundary integral equations over two-dimensional manifolds in R3. E.g., certain kinds of elliptic partial differential equations can be transformed into boundary integral equations. But unfortunately, the numerical treatment of these equations leads, in contrast to partial differential equations, to dense linear systems of equations. They are usually better conditioned than second order partial differential equations. The major drawbacks of boudary integral methods are the evaluation of singular integrals and the handling of the huge dense matrices.

In this project we investigate several methods to overcome the second obstruction. Our focus lies on fast summantion methods and multi-scale methods. Panel clustering and the fast multipole method belong to the first category, wavelet base matrix compression to the second.

In realistic applications the geometry looks rather complicated. A sequence of triangulations for such an object is given below:

Panel clustering

This method can be seen as an approximative factorization of the stiffness-matrix. Therefore, an application of the dense matrix can be approximated by three applications of sparse matrices:
A = +

For the approximative factorization, we use addition-theorems for the underlying singularity-function. By this, we have a local separation of the variables which leads to the factorization.

Fast Multipole Method

The fast multipole method has been sucessfully applied to particle interactions ( n-body problems ). We have applied this method to the boundary-element method and we have found a similar matrix-oriented interpretation of this method. Again, the dense matrix can be approximated by sparse matrices:

A = +    
Fast Multipole factorization for the Helmholtz-equation on high wavenumbers

Wavelet compression

Another way to handle the BEM-matrices is to use wavelets to compress the stiffness-matrix. Here, the wavelets are defined on the boundary and have a certain number of vanishing moments. Typical wavelet-transformation of these matrices look like the one below:

Laplace equation
original matrix wavelet-transform
Helmholtz equation
original matrix wavelet-transform
  • W. Hackbusch: Integralgleichungen, Teubner
  • W. Hackbusch, Nowak: On the fast matrix multiplication in the boundary element method by panel clustering, Numerische Mathematik (1989)
  • L. Greengard, V. Rokhlin: A fast algorithm for particle simulations Journal of Computational Physics (1987)
  • R. Schneider: Multiskalen- und Wavelets-Matrixkomporession, Teubner 1998
  • K. Giebermann: Schnelle Summationsverfahren zur numerischen Lösung von Integralgleichungen für Streuprobleme im R3
    Dissertation, Universität Karlsruhe, 1997
Related projects