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

*(English)*Zbl 0927.65063The 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.

Reviewer: R.P.Tewarson (Stony Brook)

##### MSC:

65F30 | Other matrix algorithms (MSC2010) |

15B57 | Hermitian, skew-Hermitian, and related matrices |

65F05 | Direct numerical methods for linear systems and matrix inversion |

65F50 | Computational methods for sparse matrices |