Adaptive variable-rank approximation of general matrices

Steffen Börm

Contact the author: Please use for correspondence this email.
Submission date: 06. Dec. 2005 (revised version: February 2007)
Pages: 23
published in: SIAM journal on scientific computing, 30 (2007) 1, p. 148-168 
DOI number (of the published article): 10.1137/060651173
Bibtex
MSC-Numbers: 65F30, 65N38
Keywords and phrases: hierarchical matrices, data-sparse approximation, non-local operators
Download full preprint: PDF (307 kB), PS ziped (268 kB)

Abstract:
In order to handle large dense matrices arising in the context of integral equations efficiently, panel-clustering approaches (like the popular multipole expansion method) have proven to be very useful. These techniques split the matrix into blocks, approximate the kernel function on each block by a degenerate expansion, and discretize this expansion in order to find an efficient low-rank approximation of each block.

Typical expansion schemes use the same expansion order in each block, and since the matrix approximation error has to be kept consistent with the discretization error, this allows us to handle matrices by algorithms with a complexity of for .

Recently, variable-order expansion schemes have been introduced, which choose different ranks for different blocks and have been demonstrated to reach a complexity of while keeping the matrix approximation error and the discretization error consistent.

This paper introduces an algorithm which can construct variable-rank approximations for general matrices without the need of an in-depth analysis of the underlying operators: the matrix is fed into the algorithm, and the algorithm approximates it up to an arbitrary precision.