Wolfgang Hackbusch (Max-Planck. Germany)

Hierarchical Matrices

Abstract

The hierarchical matrix technique applies to fully populated matrices as they arise from the discretisation of non-local operators like in the boundary element method or as the inverse of a sparse finite element matrix, provided that the underlying problems are elliptic. Using the format of the so-called hierarchical matrices (or short H-matrices) we are able to approximate the dense matrix by a data-sparse one so that the required storage is almost linear in the dimension, i.e., linear up to logarithmic factors.

Moreover, the essential operations for these matrices (matrix-vector and matrix-matrix multiplication, addition and inversion) can approximately be performed again in almost linear time. This fact offers new application, e.g., the computation of matrix functions like the exponential or the solution of matrix equations like the Riccati equation can be performed with almost optimal complexity.