In numerical mathematics, hierarchical matrices (H-matrices) are used as data-sparse approximations of non-sparse matrices. While a sparse matrix of dimension
Contents
Basic idea
Hierarchical matrices rely on local low-rank approximations: let
In order to approximate the entire matrix
Low-rank matrices are closely related to degenerate expansions used in panel clustering and the fast multipole method to approximate integral operators. In this sense, hierarchical matrices can be considered the algebraic counterparts of these techniques.
Application to integral operators
Hierarchical matrices are successfully used to treat integral equations, e.g., the single and double layer potential operators appearing in the boundary element method. A typical operator has the form
The Galerkin method leads to matrix entries of the form
where
where
with the coefficients
If we choose
Obviously, any other approximation separating the variables
Of particular interest are cross approximation techniques that use only the entries of the original matrix
Application to elliptic partial differential equations
Since the solution operator of an elliptic partial differential equation can be expressed as an integral operator involving Green's function, it is not surprising that the inverse of the stiffness matrix arising from the finite element method can be approximated by a hierarchical matrix.
Green's function depends on the shape of the computational domain, therefore it is usually not known. Nevertheless, approximate arithmetic operations can be employed to compute an approximate inverse without knowing the function explicitly.
Surprisingly, it is possible to prove that the inverse can be approximated even if the differential operator involves non-smooth coefficients and Green's function is therefore not smooth.
Arithmetic operations
The most important innovation of the hierarchical matrix method is the development of efficient algorithms for performing (approximate) matrix arithmetic operations on non-sparse matrices, e.g., to compute approximate inverses, LU decompositions and solutions to matrix equations.
The central algorithm is the efficient matrix-matrix multiplication, i.e., the computation of
Taking advantage of the block structure, the inverse can be computed by using recursion to compute inverses and Schur complements of diagonal blocks and combining both using the matrix-matrix multiplication. In a similar way, the LU decomposition can be constructed using only recursion and multiplication. Both operations also require
H2-matrices
In order to treat very large problems, the structure of hierarchical matrices can be improved: H2-matrices replace the general low-rank structure of the blocks by a hierarchical representation closely related to the fast multipole method in order to reduce the storage complexity to
In the context of boundary integral operators, replacing the fixed rank
Arithmetic operations like multiplication, inversion, Cholesky or LR factorization of H2-matrices can be implemented based on two fundamental operations: the matrix-vector multiplication with submatrices and the low-rank update of submatrices. While the matrix-vector multiplication is straightforward, implementing efficient low-rank updates with adaptively optimized cluster bases poses a significant challenge
Software
HLib is a C software library implementing the most important algorithms for hierarchical and
AHMED is a C++ software library that can be downloaded for educational purposes.
HLIBpro is an implementation of the core hierarchical matrix algorithms for commercial applications.
H2Lib is an open source implementation of hierarchical matrix algorithms intended for research and teaching.
awesome-hierarchical-matrices is a repository containing a list of other H-Matrices implementations.