MiS Preprint Repository

A class of matrices (H-matrices) has recently been introduced by one of the authors. These matrices have the following properties: (i) They are sparse in the sense that only few data are needed for their representation. (ii) The matrix-vector multiplication is of almost linear 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 are again of almost linear complexity. (iv) The same statement holds for the inverse of an H-matrix. The term "almost linear complexity" used above means that estimates are given by O(n log^a n): The logarithmic factor can be avoided by a further improvement, which is described in the present paper. We prove that the storage requirements and the cost of the matrix-vector multiplication is strictly linear in the dimension n; while still (full) system matrices of the boundary element method can be approximated up to the discretisation error.