Hierarchical Matrices

Frequently Asked Questions

1. Basics
   1. What is a hierarchical matrix?
   2. Where can I find a good introduction?
   3. Is there software available?
2. Arithmetics
   1. Can I control the storage requirements when performing H-matrix arithmetics?
   2. Can I control the precision when performing H-matrix arithmetics?
3. Integral equations
   1. What kinds of integral equations can be treated by hierarchical matrices?
   2. I want to use hierarchical matrices in an existing code for integral equations. How much programming would be required?
   3. How are hierarchical matrices related to panel clustering algorithms and multipole methods?
4. Partial Differential Equations
   1. What types of partial differential equations can be treated by hierarchical matrices?
   2. I want to use hierarchical matrices in my existing code for partial differential equations. How much programming would be required?
   3. Should I use the H-matrix inverse or the H-matrix LU factorization when solving elliptic partial differential equations?
5. HLib
   1. What is HLib?
   2. Is it free?
   3. What platforms are supported?
   4. Is there a documentation for HLib?

Answers

What is a hierarchical matrix?
Hierarchical matrices (or short H-matrices) are efficient data-sparse 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 low-rank 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 H-matrices 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 H-matrix arithmetics?
Yes, you can do so by using fixed-rank 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 H-matrix arithmetics?
Yes, by using adaptive-rank 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 H-matrix 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²-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²-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 low-rank approximations, so the approximation schemes are similar and typically the resulting matrices turn out to be of H-matrix structure. Fast multipole methods lead to a structure similar to that of H²-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 H-matrix. 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 H-matrix inverse or the H-matrix 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 matrix-valued Dunford-Cauchy 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 lower-level algebraic operations. The library contains functions for H- and H²-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.