Hierarchical Matrices

Literature

2007

[Börm2007b]
Steffen Börm: Construction of data-sparse H²-matrices by hierarchical compression
From an algorithmic point of view, H-matrices have a relatively simple structure: the matrix is split into a hierarchy of submatrices, and each submatrix is approximated by low rank. Since all submatrices are independent, simple recursive algorithms can be used to perform various operations. H²-matrices introduce an additional multilevel structure that can significantly improve the efficiency, but until now also meant that algorithms had to preserve the connections between different levels and blocks. This paper introduces a simple procedure that turns an H-matrix into an H²-matrix and has the advantage that it can compress each submatrix as soon as it becomes available, thus reducing the storage requirements to those of native H²-matrix algorithms without sacrificing the simplicity of H-matrix algorithms.
MPI

[Börm2007a]
Steffen Börm: Approximation of solution operators of elliptic partial differential equations by H- and H²-matrices
A major advantage of hierarchical matrix methods compared to multigrid techniques is that they can handle jumping and anisotropic coefficients without the need of specially adapted algorithms. This paper improves the first approximation estimate of [Bebendorf/Hackbusch2003] and extends it to H²-matrices.
MPI

2006

[Djokic2006]
Jelena Djokic: Efficient update of hierarchical matrices in the case of adaptive discretisation schemes
Ph.D. thesis, accepted 2006 by the University of Leipzig
If the mesh underlying a boundary element discretization of an integral operator is locally refined, it is desirable to compute the corresponding stiffness matrix also by a local update. This thesis demonstrates that this goal can be achieved for H- and H²-matrices by using appropriate clustering and discretization techniques.
PDF, 1333 KB

[Schreittmiller2006]
Robert Schreittmiller: Zur Approximation der Lösungen elliptischer Systeme partieller Differentialgleichungen mittels Finiter Elemente und H-Matrizen
Ph.D. thesis, accepted 2006 by the Technical University of Munich
This thesis extends the proof of [Bebendorf/Hackbusch2003] to elliptic systems of partial equations arising, e.g., from problems in linear elasticity.
PDF, 1529 KB

2005

[Börm2005b]
Steffen Börm: Adaptive variable-rank approximation of general dense matrices
The goal of variable-order schemes [Sauter2000] is to find data-sparse approximations of optimal complexity O(n) which ensure that the approximation error is proportional to the discretization error. The analysis of these schemes is usually quite complicated and closely connected to the underlying continuous problem. This paper presents an algorithm which finds variable-rank approximations of general matrices automatically: if the given matrix can be represented by an H²-matrix of variable rank, the algorithmus will find such a representation without any additional input from the user.
MPI

[Hackbusch2005]
Wolfgang Hackbusch: Hierarchische Matrizen - Algorithmen und Analysis
This is the script for a lecture series on hierarchical matrices. It presents the basic ideas and structures and also mentions a number of current topics like Kronecker matrices and cross approximation techniques. The script is a work in progress and written in German.
MPI

[Börm2005]
Steffen Börm: Data-sparse approximation of non-local operators by H²-matrices
H²-matrices reach their high efficiency by exploiting a nested structure of the expansion systems used for the approximation of admissible blocks. For classical integral operators, the existence of suitable nested systems is obvious, but for more general situations, a careful analysis is required. This paper presents the necessary theoretical results and uses them to prove that classical integral operators and solution operators of elliptic partial differential equations can be approximated by H²-matrices.
MPI

2004

[Börm/Grasedyck2004]
Steffen Börm, Lars Grasedyck: Hybrid cross approximation of integral operators.
A popular approach to constructing low-rank approximations of discretized integral operators is based on the application of cross approximation techniques [Tyrtyshnikov2000], [Bebendorf/Rjasanow2003] to entries of the discrete matrix. This has the advantage that a complete H-matrix approximation can be created based only on a routine for evaluating integrals and some geometric information. Unfortunately, this approach can be shown to fail in a number of important situations, e.g., for the classical double layer operator on polygonal domains. This is due to the fact that too much information is lost in the transition from the continuous to the discrete problem. The paper [Börm/Grasedyck2004] proposes a different approach: the cross approximation is applied to the original kernel function, and the resulting kernel expansion is then discretized. The paper gives a rigorous proof for the convergence of this approach and numerical experiments which indicate that the hybrid technique is both faster and more reliable than previous methods.
MPI

[Börm/Grasedyck/Hackbusch2004]
Steffen Börm, Lars Grasedyck, Wolfgang Hackbusch: Hierarchical matrices
These are the lecture notes of the winterschool on hierarchical matrices. We cover low-rank approximation schemes, clustering techniques, truncated arithmetics, complexity estimates, H²-matrices and the application of these techniques to integral operators, elliptic partial differential equations and control theory. The lectures notes also contain a description of the basic and some of the more advanced functions and structures of the HLib package and a number of theoretical and practical exercises.
MPI

[Börm2004]
Steffen Börm: Approximation of integral operators by H²-matrices with adaptive bases
The H²-matrices constructed by interpolation [Börm/Hackbusch2002a] will typically contain a degree of redundancy, since the general polynomial approximation scheme cannot take special properties of the geometry of the kernel function into account. This paper presents two algorithms that can be used to improve the efficiency: Orthogonalization detects expansion functions that have become irrelevant during the discretization, while recompression takes the kernel function into account.
PDF, 190 KB

[Börm2004a]
Steffen Börm: H²-matrix arithmetics in linear complexity
One of the main advantages of hierarchical matrices lies in the fact that arithmetic operations like matrix addition, multiplication and inversion can be performed in almost linear complexity. "Almost" linear complexity means that additional logarithmic factors appear in theory and practice. While this is natural for hierarchical matrices, it is not for H²-matrices. This paper presents algorithms that compute best approximations of sums and products of H²-matrices in linear complexity. Numerical experiments demonstrate the practical advantages of the new methods compared to general H-matrix arithmetics.
MPI

[Grasedyck2004]
Lars Grasedyck: Adaptive recompression of H-matrices for BEM
The approximation constructed by ACA will typically not be the optimal representation of a given integral operator in the hierarchical matrix format. This paper introduces an improved ACA algorithm and a coarsening technique that lead to a significant reduction of the storage complexity.
MPI

[Grasedyck/Hackbusch/LeBorne2004]
Lars Grasedyck, Wolfgang Hackbusch, Sabine LeBorne: Adaptive Geometrically Balanced Clustering of H-Matrices
The theory in [Grasedyck/Hackbusch2003] covers the case of adaptively refined meshes to define the H-matrix arithmetic, but it is fixed to a single grid and cannot exploit the fact that the grid is partially refined several times. We introduce an efficient update procedure that can assemble the BEM stiffness matrix for (locally) refined grids using a previously assembled stiffness matrix on a coarser grid.
MPI

2003

[Bebendorf/Hackbusch2003]
Mario Bebendorf, Wolfgang Hackbusch: Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with L^oo-coefficients
Numerische Mathematik (2003), 95:1-28
The problem of finding a good approximation of the inverse of a finite element stiffness matrix is similar to that of finding local low-rank approximations of the integral operator defined by the corresponding Green function. In this paper, these approximations are constructed for elliptic operators with non-smooth coefficients.
MPI

[Grasedyck/Hackbusch2003]
Lars Grasedyck, Wolfgang Hackbusch: Construction and Arithmetics of H-Matrices
Computing (2003), 70:295-334
The complexity of the H-matrix arithmetics (addition, multiplication, inversion) is estimated in a general and rigorous framework. The proofs are based on standard geometric (regular) clustering and cover the field of finite element as well as boundary element discretisations on non-regular (locally refined) grids in arbitrary dimension.
MPI

[Grasedyck/Hackbusch/Khoromskij2003]
Lars Grasedyck, Wolfgang Hackbusch, Boris Khoromskij: Solution of large-scale algebraic matrix Riccati equations by use of hierarchical matrices
Computing (2003), 70:121-165
The H-matrix arithmetic can be applied to matrix equations from control theory if the solution and all intermediate results can be represented in the hierarchical matrix format. This paper gives a rigorous proof of the approximability of the solutions of algebraic matrix Riccati equations.
MPI

[Bebendorf/Rjasanow2003]
Mario Bebendorf, Sergej Rjasanow: Adaptive low-rank approximation of collocation matrices
Computing (2003), 70:1-24
This paper describes a variant of the ACA algorithm and investigates its convergence in the case of integral operators that have been discretized by a collocation method. The paper also introduces an partitioning strategy for matrices that reduces the number of blocks but is no longer compatible with the hierarchical matrix structure.

[Löhndorf2003]
Maike Löhndorf: Effiziente Behandlung von Integraloperatoren mit H²-Matrizen variabler Ordnung
Ph.D. thesis, accepted 2003 by the University of Leipzig
This thesis covers the approximation of boundary integral operators, specifically of the classical double layer potential, by variable-order interpolation. Storing the resulting matrices in the H²-matrix format leads to a method with linear storage complexity und linear computational complexity for the matrix-vector multiplication.
PDF, 1254 KB

2002

[Börm/Hackbusch2002]
Steffen Börm, Wolfgang Hackbusch: Data-sparse approximation by adaptive H²-matrices
Computing (2002), 69:1-35
While finding the best approximation of an arbitrary matrix in a suitable hierarchical matrix format is a straightforward application of the singular value decomposition, the situation is much more complicated for H²-matrices, since we can not approximate all blocks independently, and have to ensure that the approximation spaces are nested. This paper describes and analyzes an algorithm that finds a quasi-optimal approximation of an arbitrary matrix in the H²-matrix format.
PDF, 303 KB

[Börm/Hackbusch2002a]
Steffen Börm, Wolfgang Hackbusch: H²-matrix approximation of integral operators by interpolation
Technical Report 72, Max-Planck-Institut für Mathematik in den Naturwissenschaften, 2002
The construction introduced in [Giebermann2001] can be used to create H²-matrices. The resulting algorithms are very fast and can be applied to arbitrary geometries and arbitrary asymptotically smooth kernel functions.
PDF, 121 KB

2001

[Grasedyck2001]
Lars Grasedyck: Theorie und Anwendungen Hierarchischer Matrizen
Ph.D. thesis, accepted 2001 by the University of Kiel
This thesis gives an introduction to the theory of hierarchical matrices, covering the approximation of integral operators, the arithmetic operations and very general complexity estimates based on the concepts of sparsity and idempotence of block cluster trees. It also provides error estimates for arithmetic operations.
PDF, 1411 KB   PS, 1312 KB

[Giebermann2001]
Klaus Giebermann: Multilevel approximation of boundary integral operators
Computing, 67:183-207, 2001
In this paper, the author introduces a multilevel strategy for approximating integral operators by nested interpolation. This approach is closely related to the interpolation methods used to provide initial approximations for current H²-matrix techniques.

2000

[Hackbusch/Khoromskij2000]
Wolfgang Hackbusch, Boris Khoromskij: A sparse H-matrix arithmetic. Part 2: Application to multi-dimensional problems.
Computing (2000), 64:21-47
The topic of this paper is the generalization of the basic H-matrix concepts, in particular of the complexity estimates, to the multi-dimensional setting.
MPI

[Tyrtyshnikov2000]
Eugene Tyrtyshnikov: Incomplete cross approximation in the mosaic-skeleton method
Computing (2000), 64:367-380
This paper describes a method for finding low-rank approximations of admissible blocks by looking for subspaces corresponding to maximal volumes. The resulting approximations are closely related to the adaptive cross approximation technique [Bebendorf/Rjasanow2003].

[Sauter2000]
Stefan Sauter: Variable order panel clustering
Computing (2000), 64:223-261
This paper introduces and analyzes an algorithm for the approximation of certain integral operators which ensures the optimal order of convergence of the discretization scheme with the optimal order of complexity. This remarkable result is due to the fact that a low-order expansion is sufficient on geometrically small domains, while higher orders are only required on large domains.

1999

[Hackbusch/Khoromskij/Sauter1999]
Wolfgang Hackbusch, Boris Khoromskij, Stefan Sauter: On H²-matrices
Lectures on Applied Mathematics (2002), page 9-29, Springer Berlin
This is the first paper on H²-matrices, a specialized variant of hierarchical matrices that combines the hierarchical block structure with a hierarchy of subspaces in order to improve the efficiency of the representation.
MPI

[Hackbusch1999]
Wolfgang Hackbusch: A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices.
Computing (1999), 62:89-108
This is the first paper ever written on hierarchical matrices. All the basic concepts of the H-matrix arithmetic are introduced for a simple one-dimensional model problem with rank-one approximations of the admissible blocks.
PDF, 207 KB