A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices (Q1293471)

The concept of hierarchical matrices \(\mathfrak H \) is introduced. This paper is the first of a series that will be devoted to the \(\mathfrak H \)-matrices. These matrices are not sparse in the sense that there are only few non-zero entries, but they are data-sparse -- the matrices are described by only few data. The other properties of such matrices are that the matrix-vector multiplication is of almost linear complexity, and sums and products of the matrices are not in the same set, but their truncation to the \(\mathfrak H\)-matrix format are of almost linear complexity. The same statement holds for the inverse of an \(\mathfrak H\)-matrix. Two new concepts are introduced. These allow the exact inversion of tridiagonal matrices and the approximation of some discrete integral operators.