Hierarchical Matrices
Frequently Asked Questions
 Basics
 What is a hierarchical matrix?
 Where can I find a good introduction?
 Is there software available?
 Arithmetics
 Can I control the storage requirements when performing
Hmatrix arithmetics?
 Can I control the precision when performing
Hmatrix arithmetics?
 Integral equations
 What kinds of integral equations can be treated
by hierarchical matrices?
 I want to use hierarchical matrices in an existing
code for integral equations. How much programming would be
required?
 How are hierarchical matrices related to panel
clustering algorithms and multipole methods?
 Partial Differential Equations
 What types of partial differential equations can be
treated by hierarchical matrices?
 I want to use hierarchical matrices in my existing
code for partial differential equations. How much programming would
be required?
 Should I use the Hmatrix inverse or the
Hmatrix LU factorization when solving elliptic partial
differential equations?
 HLib
 What is HLib?
 Is it free?
 What platforms are supported?
 Is there a documentation for HLib?
Answers
What is a hierarchical matrix?
Hierarchical matrices (or short Hmatrices) are efficient
datasparse representations of certain densely populated matrices.
The basic idea is to split a given matrix into a hierarchy of rectangular
blocks and approximate each of the blocks by a lowrank matrix.
Based on this structure, approximative algorithms for matrix arithmetics,
inversion, preconditioning and even matrix equations can be introduced
that work in almost optimal complexity.
Where can I find a good introduction?
The lecture notes
[Börm/Grasedyck/Hackbusch2004] of the winterschools on hierarchical
matrices explain all basic concepts.
Is there software available?
Yes. HLib was the first library and has
been used successfully by many scientists for partial differential equations,
control problems, integral equations and matrix functions. There are also
a library by Ronald Kriemann that focuses on parallelization of
Hmatrices and a library by Mario Bebendorf and Sergej Rjasanow
that contains the original implementation of the ACA algorithm
[Bebendorf/Rjasanow2003].
Can I control the storage requirements when performing
Hmatrix arithmetics?
Yes, you can do so by using fixedrank arithmetics, i.e., by prescribing
an upper bound for the rank of the matrices produced by truncation procedures.
Can I control the precision when performing
Hmatrix arithmetics?
Yes, by using adaptiverank arithmetics. The truncation procedures compute
all singular values of a given matrix, so it is possible to drop only those
values that lie below a given tolerance.
What kinds of integral equations can be treated
by hierarchical matrices?
Hierarchical matrices work if the kernel function can be approximated
by local expansions and if the discretization uses local basis functions.
Any integral equation with standard finite elements and asymptotically
smooth kernels should pose no problem at all.
I want to use hierarchical matrices in an existing
code for integral equations. How much programming would be
required?
If you use HLib, there are several answers:
Our ACA
[Bebendorf/Rjasanow2003] implementation uses some sophisticated heuristics
to compute an Hmatrix approximation of a matrix using only a
relatively small number of entries of the original matrix, so you can simply
plug your existing routine into the library.
If you need the higher performance and lower storage requirements of
H^{2}matrices, you can either convert the matrix created
by ACA to this format by calling the appropriate function or write routines
that evaluate your kernel function and integrate Lagrange polynomials to
create the H^{2}matrix directly
[Börm/Hackbusch2002a].
In order to be able to create a suitable cluster tree, you also have to
supply the library with some geometric information.
How are hierarchical matrices related to panel
clustering algorithms and multipole methods?
Closely. Both techniques are based on local lowrank approximations, so the
approximation schemes are similar and typically the resulting matrices turn
out to be of Hmatrix structure. Fast multipole methods lead to
a structure similar to that of H^{2}matrices.
The main advantage of hierarchical matrices is that they provide arithmetic
operations, so we can efficiently construct good preconditioners or reduce
the storage requirements by purely algebraic algorithms.
What types of differential equations can be treated
by hierarchical matrices?
There are proofs for elliptic differential equations with
L^{oo}coefficients
[Bebendorf/Hackbusch2003]
and control problems based on elliptic operators
[Grasedyck/Hackbusch/Khoromskij2003].
I want to use hierarchical matrices in my existing
code for partial differential equations. How much programming would
be required?
If you use HLib, only a small amount of
"glue logic" should be required: You write the sparse matrix of the
discretized operator into the appropriate data structure of our library
and call a routine that transforms it into an Hmatrix. Then you
can compute its approximate LU decomposition or inverse by calling the
corresponding functions.
In order to be able to create a suitable cluster tree, you also have to
supply the library with some geometric information.
Should I use the Hmatrix inverse or the Hmatrix
LU factorization when solving elliptic partial differential
equations?
The construction of the LU factorization takes less time than that of
the approximate inverse. You should compute the inverse only if you
are interested in performing additional operations with it, e.g.,
when solving matrix equations or approximating the matrixvalued
DunfordCauchy integral.
What is HLib?
HLib is a library for hierarchical matrices that was written
by Lars Grasedyck and Steffen Börm.
Most routines are written in the C programming language
using BLAS and
LAPACK for lowerlevel
algebraic operations.
The library contains functions for H and
H^{2}matrix arithmetics, the treatment of partial
differential equations and a number of integral operators as well as
support routines for the creation of cluster trees, visualization
and numerical quadrature.
This is a work in progress, so there may be undiscovered errors
and you can expect new features to appear with every new release.
Is it free?
Yes, but only for research purposes. You just have to print out and sign
the license agreement and send it to the specified
address, and we will send you the source code of the library.
What platforms are supported?
We currently use Linux and different versions of Solaris^{TM},
but we have also succesfully tested the library on Irix^{TM} and
Tru64 Unix^{TM}.
Compiling for Windows^{TM} should pose no problems as long as
BLAS
and LAPACK libraries
are available.
Is there a documentation for HLib?
There are the
lecture notes of the annual winter schools on hierarchical matrices.
They contain a description of the basic data structures and routines
as well as the theoretical foundations necessary to understand them.
