Compression method for boundary integral matrices with translation-invariant kernel functions
Final Report Abstract
The mathematical investigation of electrostatic, electromagnetic, or acoustic fields and of structural mechanics can be reduced to boundary integral equations. Compared to partial differential equations and finite element methods, this approach offers the advantage that only the surface has to be discretized, but not the entire volume, so that we can reach a given accuracy at a considerably lower number of degrees of freedom. A major disadvantage of the boundary integral formulation is that it involves nonlocal operators, i.e., that it connects every point on the surface with any other point. After the discretization, this generally leads to dense matrices, while partial differential equations lead to sparse matrices. Compression techniques can be used to handle these dense matrices efficiently. These techniques usually rely on the fact that the kernel function g is locally smooth and can therefore be approximated by polynomials, thus reducing memory requirements and computation time. This project investigates how interpolation can be used to approximate the dense matrix efficiently by an H2 -matrix. Of particular interest is the translation invariance of the kernel function, expressed by the equation g(x, y) = g(x − c, y − c). By choosing the domains of interpolation appropriately, a very small number of coefficients is sufficient to describe all interactions within well-separated subdomains. Applied to typical boundary element matrices, interpolation leads to unnecessarily large ranks that can be reduced using algebraic compression techniques without significantly reducing the accuracy. The efficient implementation of these compression techniques for translation-invariant kernel functions was a major focus in this project. We were able to reduce the computational work for all non-leaf levels from O(nk 2 ) to O(k 3 log n). A particular challenge is posed by the boundary integral equation for the high-frequency Helmholtz equation describing the scattering of acoustic waves, since it involves a highly oscillatory kernel function. The final phase of this project is dedicated to applying the translation-invariant compression algorithm to the high-frequency Helmholtz equation. We have managed to reduce the storage complexity from O(nk 2 log n) to O(nk 2 ), allowing us to treat significantly larger matrices in the given amount of available storage.
Publications
-
Memory efficient compression of DH2-matrices for high frequency Helmholtz problems. Numerical Linear Algebra with Applications, 31(6).
Börm, Steffen & Henningsen, Janne
