On the best approximation of the hierarchical matrix product

DOI10.1137/18M1189373arXiv1805.08998WikidataQ128473200 ScholiaQ128473200MaRDI QIDQ6301976FDOQ6301976

H. Harbrecht, Michael Peters, Jürgen Dölz

Publication date: 23 May 2018

Abstract: The multiplication of matrices is an important arithmetic operation in computational mathematics. In the context of hierarchical matrices, this operation can be realized by the multiplication of structured block-wise low-rank matrices, resulting in an almost linear cost. However, the computational efficiency of the algorithm is based on a recursive scheme which makes the error analysis quite involved. In this article, we propose a new algorithmic framework for the multiplication of hierarchical matrices. It improves currently known implementations by reducing the multiplication of hierarchical matrices towards finding a suitable low-rank approximation of sums of matrix-products. We propose several compression schemes to address this task. As a consequence, we are able to compute the best-approximation of hierarchical matrix products. A cost analysis shows that, under reasonable assumptions on the low-rank approximation method, the cost of the framework is almost linear with respect to the size of the matrix. Numerical experiments show that the new approach produces indeed the best-approximation of the product of hierarchical matrices for a given tolerance. They also show that the new multiplication can accomplish this task in less computation time than the established multiplication algorithm without error control.

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

This page was built for publication: On the best approximation of the hierarchical matrix product

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6301976)