Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.
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.
