Hierarchical Matrices
Literature
2014
[Kriemann2014]
R. Kriemann:
HLU factorization on manycore systems.
The HLU factorization is a very important algorithm
for the construction of robust Hmatrix preconditioners
for BEM and FEM problems.
This paper describes how the construction of the factorization can
be implemented efficiently on a manycore system by using a
taskgraph approach.
MPI
[BörmReimer2014]
S. Börm, K. Reimer:
Efficient arithmetic operations for rankstructured matrices based on
hierarchical lowrank updates.
to appear in Comp. Vis. Sci.
Most arithmetic algorithms for Hmatrices are based on a sequence
of lowrank updates that are applied to submatrices of a given
Hmatrix.
This paper introduces an algorithm that performs similar updates on
H²matrices in linear time and shows how it can
be used to develop efficient arithmetic routines for H²matrices.
Numerical experiments demonstrate that the new approach leads to
preconditioners for FEM and BEM problems that require
O(n log n) operations for setup and, at least for twodimensional
problems, O(n) units of storage.
arXiv.org
[BebendorfKuskeVenn2014]
M. Bebendorf, C. Kuske, R. Venn:
Wideband nested cross approximation for Helmholtz problems.
Num. Math. (2014)
Treating medium to highfrequency Helmholtz equations by standard
Hmatrix techniques leads to very high local ranks and makes
this approach rather unattractive.
This paper combines the idea of directional decompositions introduced
in [EngquistYing2007] with the
nested ACA algorithm presented in
[BebendorfVenn2012]:
factoring out plane waves leads to kernel functions that are smooth
in a cone originating in a cluster, so ACA can be expected to be
appropriate for these functions.
Since plane waves are separable, the same holds for the original
functions.
The resulting algorithm uses a heuristic to choose representative
columns of the total cluster basis for the cones and reaches
a complexity of O(n log n).
SpringerLink
[BörmChristophersen2014]
S. Börm, S. Christophersen:
Approximation of integral operators by Green quadrature and nested cross
approximation.
The Green quadrature method (cf.
[BörmGördes2014]) can lead to relatively high ranks,
particularly in threedimensional applications.
This paper combines this approach with a cross approximation technique
in order to obtain a fast algorithm that construct an approximation
of a boundary integral element matrix in linear complexity.
arXiv.org
2013
[BörmGördes2013]
S. Börm, J. Gördes:
Lowrank approximation of integral operators using the Green formula and quadrature.
Num. Alg. 64(3):567592 (2013)
Boundary element methods typically rely on a representation formula
that expresses the solution of a partial differential equation by
boundary integrals.
This property can also be used to construct lowrank approximations
by applying quadrature rules to the surfaces of suitable subdomains.
This paper introduces the corresponding algorithm and proves that
it converges exponentially.
SpringerLink
2012
[BebendorfVenn2012]
M. Bebendorf, R. Venn:
Constructing nested bases approximations from the entries of
nonlocal operators.
Num. Math. (2012), 121(4):609635
This paper presents an extension of the ACA algorithm
(cf. [BebendorfRjasanow2003])
to H²matrices: the total cluster bases
(cf. [Börm2005]) are replace by
a cross approximation relying on a heuristic choice of
representative columns.
SpringerLink
2010
[Börm2010]
Steffen Börm:
Efficient Numerical Methods for Nonlocal Operators:
H²Matrix Compression, Algorithms and Analysis.
EMS Tracts in Mathematics, Vol. 14 (2010)
H²matrices can be used as datasparse representations of
dense matrices resulting, e.g., from the discretization of an
integral or elliptic partial differential operator.
This book offers a comprehensive introduction into the relevant
algorithms, the techniques for the corresponding complexity
and error analysis, and a collection of numerical examples
illustrating the properties of the H²matrix method.
EMS
2009
[GrasedyckKriemannLeBorne]
L. Grasedyck, R. Kriemann, S. Le Borne:
Domaindecomposition based HLU preconditioning.
Num. Math. 112(4):565600 (2009)
The performance of triangular factorizations can be improved
significantly by using a nested dissection ordering.
This paper describes how to construct a nested dissection cluster
tree and use it to obtain efficient HLU factorizations
that can be used as preconditioners for partial differential
equations.
SpringerLink
[Hackbusch2009]
Wolfgang Hackbusch:
Hierarchische Matrizen: Algorithmen und Analysis.
This book gives a comprehensive overview of the current state
of the art in the field of hierarchical matrices.
It covers algebraic and analytic compression techniques,
matrix arithmetic operations, treatment of matrix functions and
a new type of multilevel domain decomposition method based on
approximations of local PoincaréSteklov operators.
SpringerLink
2007
[EngquistYing2007]
B. Engquist, L. Ying:
Fast directional multilevel algorithms for oscillatory kernels
SIAM J. Sci. Comput., 29(4):17101737 (2007)
Applying H or H²methods directly to Helmholtz
problems with large wave numbers leads to relatively high local ranks,
which results in poor compression results.
This paper presents an alternative approach:
the Helmholtz kernel function is split into a plane wave and a factor
that is smooth in a cone originating from a given cluster.
This smooth factor can be approximated by standard techniques, and
combining the resulting expansions on different levels of the cluster
tree leads to an algorithm of complexity O(n log n).
SIAM
[Börm2007b]
Steffen Börm:
Construction of datasparse H^{2}matrices by
hierarchical compression
SIAM J. Sci. Comput., 31:18201839 (2009)
From an algorithmic point of view, Hmatrices 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 Hmatrix
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 Hmatrix algorithms.
MPI,
SIAM
[Börm2007a]
Steffen Börm:
Approximation of solution operators of elliptic partial differential
equations by H and H²matrices
Num. Math. 115:165193 (2010)
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,
SpringerLink
2005
[Börm2005b]
Steffen Börm:
Adaptive variablerank approximation of general dense matrices
SIAM J. Sci. Comput. 30:148168 (2007)
The goal of variableorder schemes
[Sauter2000] is to find datasparse
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 variablerank
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,
SIAM
[Börm2005]
Steffen Börm:
Datasparse approximation of nonlocal operators by H²matrices
Lin. Alg. Appl. 422:380403 (2007)
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,
ScienceDirect
2004
[Börm/Grasedyck2004]
Steffen Börm, Lars Grasedyck:
Hybrid cross approximation of integral operators.
Num. Math. 101:221249 (2005)
A popular approach to constructing lowrank 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
Hmatrix 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,
SpringerLink
[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 lowrank 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
Computing 74:249271 (2005)
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.
MPI,
SpringerLink
[Börm2004a]
Steffen Börm:
H²matrix arithmetics in linear complexity
Computing 77:128 (2006)
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 Hmatrix arithmetics.
MPI,
SpringerLink
[Grasedyck2004]
Lars Grasedyck:
Adaptive recompression of Hmatrices for BEM
Computing 74(3):205223 (2005)
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,
SpringerLink
2003
[Bebendorf/Hackbusch2003]
Mario Bebendorf, Wolfgang Hackbusch:
Existence of Hmatrix approximants to the inverse FEmatrix
of elliptic operators with L^{oo}coefficients
Num. Math. (2003), 95:128
The problem of finding a good approximation of the inverse of a
finite element stiffness matrix is similar to that of finding local
lowrank approximations of the integral operator defined by the
corresponding Green function. In this paper, these approximations
are constructed for elliptic operators with nonsmooth coefficients.
MPI,
SpringerLink
[Grasedyck/Hackbusch2003]
Lars Grasedyck, Wolfgang Hackbusch:
Construction and Arithmetics of HMatrices
Computing (2003), 70:295334
The complexity of the Hmatrix 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
nonregular (locally refined) grids in arbitrary dimension.
MPI,
SpringerLink
[Grasedyck/Hackbusch/Khoromskij2003]
Lars Grasedyck, Wolfgang Hackbusch, Boris Khoromskij:
Solution of largescale algebraic matrix Riccati equations by
use of hierarchical matrices
Computing (2003), 70:121165
The Hmatrix 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,
SpringerLink
[Bebendorf/Rjasanow2003]
Mario Bebendorf, Sergej Rjasanow:
Adaptive lowrank approximation of collocation matrices
Computing (2003), 70:124
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.
SpringerLink
2002
[Börm/Hackbusch2002]
Steffen Börm, Wolfgang Hackbusch:
Datasparse approximation by adaptive H²matrices
Computing (2002), 69:135
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 quasioptimal
approximation of an arbitrary matrix in the H²matrix
format.
MPI,
SpringerLink
[Börm/Hackbusch2002a]
Steffen Börm, Wolfgang Hackbusch:
H²matrix approximation of integral operators by
interpolation
Appl. Num. Math. (2002), 43:129143
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.
MPI,
ScienceDirect
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 (2822 KB)
[Giebermann2001]
Klaus Giebermann:
Multilevel approximation of boundary integral operators
Computing, 67:183207, 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.
SpringerLink
2000
[Hackbusch/Khoromskij2000]
Wolfgang Hackbusch, Boris Khoromskij:
A sparse Hmatrix arithmetic. Part 2: Application to multidimensional
problems.
Computing (2000), 64:2147
The topic of this paper is the generalization of the basic Hmatrix
concepts, in particular of the complexity estimates, to the multidimensional
setting.
MPI,
SpringerLink
[Tyrtyshnikov2000]
Eugene Tyrtyshnikov:
Incomplete cross approximation in the mosaicskeleton method
Computing (2000), 64:367380
This paper describes a method for finding lowrank 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].
SpringerLink
[Sauter2000]
Stefan Sauter:
Variable order panel clustering
Computing (2000), 64:223261
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 loworder expansion
is sufficient on geometrically small domains, while higher orders are
only required on large domains.
MPI (extended),
SpringerLink
1999
[Hackbusch/Khoromskij/Sauter1999]
Wolfgang Hackbusch, Boris Khoromskij, Stefan Sauter:
On H²matrices
Lectures on Applied Mathematics (2002), page 929, 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,
SpringerLink
[Hackbusch1999]
Wolfgang Hackbusch:
A sparse matrix arithmetic based on Hmatrices. Part I:
Introduction to Hmatrices.
Computing (1999), 62:89108
This is the first paper ever written on hierarchical matrices. All the
basic concepts of the Hmatrix arithmetic are introduced for
a simple onedimensional model problem with rankone approximations of
the admissible blocks.
PDF (415 KB),
SpringerLink
[Goreinov/Tyrtyschnikov/Zamarashkin1997]
S.A. Goreinov, E.E. Tyrtyshnikov, N.L. Zamarashkin:
A theory of pseudoskeleton approximations
Linear Algebra and its Applications (1997), 261:121
This paper demonstrates that if a matrix can be approximated by low
rank k, it can also be approximated by a matrix constructed
from k of its rows and columns (called a pseudoskeleton
approximation).
This results indicates that the related cross approximation technique
(cf. [Tyrtyshnikov2000],
[Bebendorf/Rjasanov2003])
can work if the correct rows and columns are chosen.
ScienceDirect
[Goreinov/Tyrtyshnikov/Zamarashkin1997b]
S.A. Goreinov, E.E. Tyrtyshnikov, N.L. Zamarashkin:
Pseudoskeleton approximation by matrices of maximal volume
Mathematical Notes (1997), 62:515519
This paper suggests a strategy for choosing the rows and columns
required for the pseudoskeleton approximation
(cf.
[Goreinov/Tyrtyhnikov/Zamarashkin1997].
SpringerLink
