Dölz, Jürgen and Harbrecht, Helmut and Multerer, Michael D.. (2018) On the best approximation of the hierarchical matrix product. Preprints Fachbereich Mathematik, 2018 (10).

PDF
564Kb 
Official URL: https://edoc.unibas.ch/70167/
Downloads: Statistics Overview
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 blockwise lowrank 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 lowrank approximation of sums of matrix products. We propose several compression schemes to address this task. As a consequence, we are able to compute the bestapproximation of hierarchical matrix products. A cost analysis shows that, under reasonable assumptions on the lowrank 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 bestapproximation 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.
Faculties and Departments:  05 Faculty of Science > Departement Mathematik und Informatik > Mathematik > Computational Mathematics (Harbrecht) 12 Special Collections > Preprints Fachbereich Mathematik 

UniBasel Contributors:  Dölz, Jürgen and Harbrecht, Helmut 
Item Type:  Preprint 
Publisher:  Universität Basel 
Language:  English 
edoc DOI:  
Last Modified:  11 Apr 2019 15:41 
Deposited On:  11 Apr 2019 15:41 
Repository Staff Only: item control page