We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
MiS Preprint
114/2005
Adaptive variable-rank approximation of general matrices
Steffen Börm
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 $n\times n$ matrices by algorithms with a complexity of ${\mathcal O}(n \log^\alpha n)$ for $\alpha\geq 1$.
Recently, variable-order expansion schemes have been introduced, which choose different ranks for different blocks and have been demonstrated to reach a complexity of ${\mathcal O}(n)$ 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.