Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices (Q1849565)

The authors review the definition of \(\mathcal H\) and \({\mathcal H}^2\) matrices, the first ones with an underlying cluster tree and the second one with nested bases. The \({\mathcal H}^2\)-matrices have the following properties: (1) they are data-sparse in the sense that only \({\mathcal O}(n)\) data are needed for their representation; (2) the matrix-vector multiplication is of linear complexity; and (3) sums of these matrices can be computed with linear complexity after truncation to \({\mathcal H}^2\)-matrix format. In the case of sparse matrices \(A\) resulting from finite element discretizations of elliptic boundary value problems, the inverse \(A^{-1}\) approximated by the \({\mathcal H}^2\)-format may lead to a fast iteration. An efficient implementation of some basic operations of \({\mathcal H}^2\) is considered. An algorithm is presented that computes an optimal \({\mathcal H}^2\)-approximation with only \({\mathcal O}(n^2)\) operations. If the original matrix is given in \(\mathcal H\)-format, the algorithm can be modified to use only an almost linear amount of operations. Complexity and storage requirements are considered and examples are presented.