Steffen Börm

Steffen Börm, Jens Markus Melenk

We present and analyze an approximation scheme for a class of highly oscillatory kernel functions, taking the 2D and 3D Helmholtz kernels as examples. The scheme is based on polynomial interpolation combined with suitable pre- and postmultiplication by plane waves. It is shown to converge exponentially in the polynomial degree and supports multilevel approximation techniques. Our convergence analysis may be employed to establish exponential convergence of certain classes of fast methods for discretizations of the Helmholtz integral operator that feature polylogarithmic-linear complexity.

Riccardo Hertel, Sven Christophersen, Steffen Börm

Magnetostatic field calculations in micromagnetic simulations can be numerically expensive, particularly in the case of large-scale finite element simulations. The established finite element / boundary element method (FEM/BEM) by Fredkin & Koehler involves a densely populated matrix with unacceptable numerical costs for problems involving a large number of degrees of freedom $N$. By using hierarchical matrices of $\mathcal{H}^2$ type, we show that the memory requirements for the FEM/BEM method can be reduced dramatically, effectively converting the quadratic complexity $\mathcal{O}(N^2)$ of the problem to a linear one $\mathcal{O}(N)$. We obtain matrix size reductions of nearly $99\%$ in test cases with more than $10^6$ degrees of freedom, and we test the computed magnetostatic energy values by means of comparison with analytic values. The efficiency of the $\mathcal{H}^2$-matrix compression opens the way to large-scale magnetostatic field calculations in micromagnetic modeling, all while preserving the accuracy of the established FEM/BEM formalism.

Peter Benner, Steffen Börm, Thomas Mach et al.

The computation of eigenvalues of large-scale matrices arising from finite element discretizations has gained significant interest in the last decade. Here we present a new algorithm based on slicing the spectrum that takes advantage of the rank structure of resolvent matrices in order to compute m eigenvalues of the generalized symmetric eigenvalue problem in $\mathcal{O}(n m \log^αn)$ operations, where $α>0$ is a small constant.

Steffen Börm, Maria Lopez-Fernandez, Stefan Sauter

The sparse approximation of high-frequency Helmholtz-type integral operators has many important physical applications such as problems in wave propagation and wave scattering. The discrete system matrices are huge and densely populated; hence their sparse approximation is of outstanding importance. In our paper we will generalize the directional $\mathcal{H}^{2}$-matrix techniques from the \textquotedblleft pure\textquotedblright\ Helmholtz operator $\mathcal{L}u=-Δu+ζ^{2}u$ with $ζ=-\operatorname*{i}k$, $k\in\mathbb{R}$, to general complex frequencies $ζ\in\mathbb{C}$ with $\operatorname{Re}ζ>0$. In this case, the fundamental solution decreases exponentially for large arguments. We will develop a new admissibility condition which contains $\operatorname{Re}ζ$ in an explicit way and introduce the approximation of the integral kernel function on admissible blocks in terms of frequency-dependent \textit{directional expansion functions}. We develop an error analysis which is explicit with respect to the expansion order and with respect to $\operatorname{Re}ζ$ and $\operatorname{Im}ζ$. This allows to choose the \textit{variable }expansion order in a quasi-optimal way depending on $\operatorname{Re}ζ$ but independent of, possibly large, $\operatorname{Im}ζ$. The complexity analysis is explicit with respect to $\operatorname{Re}ζ$ and $\operatorname{Im}ζ$ and shows how higher values of $\operatorname{Re}% ζ$ reduce the complexity. In certain cases, it even turns out that the discrete matrix can be replaced by its nearfield part. Numerical experiments illustrate the sharpness of the derived estimates and the efficiency of our sparse approximation.

Steffen Börm, Sven Christophersen

We consider a compression method for boundary element matrices arising in the context of the computation of electrostatic fields. Green cross approximation combines an analytic approximation of the kernel function based on Green's representation formula and quadrature with an algebraic cross approximation scheme in order to obtain both the robustness of analytic methods and the efficiency of algebraic ones. One particularly attractive property of the new method is that it is well-suited for acceleration via general-purpose graphics processors (GPUs).

Steffen Börm

Triangular factorizations are an important tool for solving integral equations and partial differential equations with hierarchical matrices ($\mathcal{H}$-matrices). Experiments show that using an $\mathcal{H}$-matrix LR factorization to solve a system of linear questions is superior to direct inversion both with respect to accuracy and efficiency, but so far theoretical estimates quantifying these advantages were missing. Due to a lack of symmetry in $\mathcal{H}$-matrix algorithms, we cannot hope to prove that the LR factorization takes one third of the operations of the inversion or the matrix multiplication, as in standard linear algebra. We can, however, prove that the LR factorization together with two other operations of similar complexity, i.e., the inversion and multiplication of triangular matrices, requires not more operations than the matrix multiplication. We can complete the estimates by proving an improved upper bound for the complexity of the matrix multiplication, designed for recently introduced variants of classical $\mathcal{H}$-matrices.

Steffen Börm

Numerical algorithms for elliptic partial differential equations frequently employ error estimators and adaptive mesh refinement strategies in order to reduce the computational cost. We can extend these techniques to general vectors by splitting the vectors into a hierarchically organized partition of subsets and using appropriate bases to represent the corresponding parts of the vectors. This leads to the concept of \emph{hierarchical vectors}. A hierarchical vector with $m$ subsets and bases of rank $k$ requires $mk$ units of storage, and typical operations like the evaluation of norms and inner products or linear updates can be carried out in $\mathcal{O}(mk^2)$ operations. Using an auxiliary basis, the product of a hierarchical vector and an $\mathcal{H}^2$-matrix can also be computed in $\mathcal{O}(mk^2)$ operations, and if the result admits an approximation with $\widetilde m$ subsets in the original basis, this approximation can be obtained in $\mathcal{O}((m+\widetilde m)k^2)$ operations. Since it is possible to compute the corresponding approximation error exactly, sophisticated error control strategies can be used to ensure the optimal compression. Possible applications of hierarchical vectors include the approximation of eigenvectors and the solution of time-dependent problems with moving local irregularities.

Steffen Börm

Standard numerical algorithms like the fast multipole method or $\mathcal{H}$-matrix schemes rely on low-rank approximations of the underlying kernel function. For high-frequency problems, the ranks grow rapidly as the mesh is refined, and standard techniques are no longer attractive. Directional compression techniques solve this problem by using decompositions based on plane waves. Taking advantage of hierarchical relations between these waves' directions, an efficient approximation is obtained. This paper is dedicated to directional $\mathcal{H}^2$-matrices that employ local low-rank approximations to handle directional representations efficiently. The key result is an algorithm that takes an arbitrary matrix and finds a quasi-optimal approximation of this matrix as a directional $\mathcal{H}^2$-matrix using a prescribed block tree. The algorithm can reach any given accuracy, and the approximation requires only $\mathcal{O}(n k + κ^2 k^2 \log n)$ units of storage, where $n$ is the matrix dimension, $κ$ is the wave number, and $k$ is the local rank. In particular, we have a complexity of $\mathcal{O}(n k)$ if $κ$ is constant and $\mathcal{O}(n k^2 \log n)$ for high-frequency problems characterized by $κ^2 \sim n$. Since the algorithm can be applied to arbitrary matrices, it can serve as the foundation of fast techniques for constructing preconditioners.

Steffen Börm, Christina Börst, Jens Markus Melenk

Butterfly algorithms are an effective multilevel technique to compress discretizations of integral operators with highly oscillatory kernel functions. The particular version of the butterfly algorithm considered here realizes the transfer between levels by Chebyshev interpolation. We present a refinement of the analysis that improves the stability estimates underlying the error bounds.

Steffen Börm, Sven Christophersen

We present a fast algorithm that constructs a data-sparse approximation of matrices arising in the context of integral equation methods for elliptic partial differential equations. The new algorithm uses Green's representation formula in combination with quadrature to obtain a first approximation of the kernel function and then applies nested cross approximation to obtain a more efficient representation. The resulting $\mathcal{H}^2$-matrix representation requires $\mathcal{O}(n k)$ units of storage for an $n\times n$ matrix, where $k$ depends on the prescribed accuracy.