We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
Lecture Note
17/2003
Data-Sparse Approximation of Integral Operators
Boris N. Khoromskij
Abstract
These notes are based on a lecture course given by the author in the winter semester of 2002--2003 for postgraduate students at the University of Leipzig. The purpose of this course was to provide an introduction to modern methods of a data-sparse approximation to integral and more general nonlocal operators based on the use of hierarchical matrices (or briefly $\mathcal{H}$-matrices).
Being a direct descendant of well established panel clustering, fast multipole and mosaic-skeleton methods, the $\mathcal{H}$-matrix technique allows in addition matrix-matrix operations of almost linear cost. As a consequence, it provides a constructive tool for the efficient matrix representation and fast matrix arithmetics in a wide range of applications. We focus on the error and complexity analysis of the $\mathcal{H}$-matrix approximation to integral operators. To summarize briefly, a class of operators with asymptotically smooth kernels can be approximated up to a tolerance $O(N^{-\alpha})$, $\alpha > 0$, by data-sparse $N \times N$ $\mathcal{H}$-matrix of almost linear complexity $O(N \log^g N)$, where $N$ is the size of a discrete problem.
We begin with a short survey on the Galerkin finite element methods for strongly elliptic variational equations. Next we give an insight to the classical polynomial approximation of multivariate functions. To proceed with, we construct a hierarchical decomposition of the product integration domain that refines adaptively towards the set of singularity points of the kernel. The polynomial interpolation allows then a patch-wise degenerate approximation to the kernel function in issue. The desired data-sparse $\mathcal{H}$-matrix approximation comes up through the finite element Galerkin method applied to the operator with a modified kernel as above.
All in all, the $\mathcal{H}$-matrix format can be specified by a list of low-rank matrix blocks within a hierarchical matrix partitioning that is refined towards the main diagonal. We discuss the key building blocks in the $\mathcal{H}$-matrix construction and prove the linear-logarithmic costs for the memory requirements and for the matrix-by-vector product. Moreover, the matrix-matrix multiplication and the $\mathcal{H}$-matrix inverse can be also implemented (approximately) within the given format, and with $O(N \log^q N)$ complexity.
The basic hierarchical format can be improved and generalised in several directions as follows:
(i) Uniform and $\mathcal{H}^2$-matrices;
(ii) blended $\mathcal{H}$-matrix approximation;
(iii) coarsening of the hierarchical format using weaker admissibility criteria;
(iv) wire-basket approximation for $\cL$-harmonic kernels;
(v) hierarchical approximation on graded meshes;
(vi) direct data-sparse representation for the Green function;
The author is grateful to Prof. Dr. W. Hackbusch for extensive joint works on the topic and for valuable discussions which have actually inspired this lecture course. I am thankful to Mrs. V. Khoromskaia for the help with typing the LaTeX-files.
