A sparse matrix arithmetic based on H-matrices. Part I : Introduction to H-matrices

A class of matrices (H-matrices) is introduced which have the following pro perties. (i) They are sparse in the sense that only few data are needed for their representation. (ii) The matrix-vector multiplication is of almost l inear complexity. (iii) In general, sums and products of these matrices are no longer in the same set, but their truncations to the H-matrix format ar e again of almost linear complexity. (iv) The same statement holds for the inverse of an H-matrix. This paper is the first of a series and is devoted to the first introductio n of the H-matrix concept. Two concret formats are described. The first one is the simplest possible. Nevertheless, it allows the exact inversion of t ridiagonal matrices. The second one is able to approximate discrete integra l operators.