-Matrices

Combining the $$\mathcal{H}$$ -matrices with of a second hierarchical structure, we are led to the $$\mathcal{H}^{2}$$ -matrices. Here the storage cost and the arithmetical cost of the matrix operations are clearly reduced. In many cases, one can avoid the logarithmic factor in the theoretical estimates. In this chapter we need some new notation introduced in Section 8.1. Next we discuss pre-versions of the $$\mathcal{H}^{2}$$ -matrix format in Sections 8.2–8.3. Section 8.4 contains the final definition of an $$\mathcal{H}^{2}$$ -matrix, requiring special nestedness conditions for a family of vector spaces. Special topics are the transfer matrices (cf. §8.4.2), transformations (cf. §8.4.4), orthonormal bases (cf. §8.4.5), SVD bases (cf. §8.4.7), and truncation (cf. §8.4.8). The characteristic nestedness condition can be inherited from the continuous problem as studied in Section 8.5. For suitable rank distributions we even prove a linear estimate of the cost without any logarithmic factor (see Section 8.6). The matrix-vector multiplication by $$\mathcal{H}^{2}$$ -matrices and the corresponding work is described in Section 8.7. The multiplication algorithm for two $$\mathcal{H}^{2}$$ -matrices is given in Section 8.9. Also in §9.3.3 we shall refer to $$\mathcal{H}^{2}$$ -matrices.