Hierarchical matrices based on a weak admissibility criterion (Q1764140)

The class of \(\mathcal{H}\)-matrices was developed to approximate nonlocal operator equations in a cheap way. Not only are those matrices sparse but they allow their computation with almost linear complexity only. In particular, \(\mathcal{H}\)-matrices are very well suited for the approximation of integral equations. However, while matrix-vector multiplication is very cheap, matrix-matrix operations are much more expensive. This fact comes mainly from a large constant which is usually surpressed by the \(\mathcal{O}\)-notation used in the comlexity estimates. This may be achieved by a simpler block partitioning in the hierarchy of the matrices and this is the main topic of the paper under review. However, allowing a more relaxed admissibility condition which leads to a simpler partitioning the authors come up with the conjecture that the complexity will stay nearly the same. This conjecture leads to the definition of new families of matrices which may play a crucial role in the arithmetic of \(\mathcal{H}\)-matrices.