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
112/2005
Approximate Iterations for Structured Matrices
Wolfgang Hackbusch, Boris N. Khoromskij and Eugene E. Tyrtyshnikov
Abstract
Important matrix-valued functions $f(A)$ are, e.g., the inverse $A^{-1}$, the square root $\sqrt{A}$, the sign function and the exponent. Their evaluation for large matrices arising from pdes is not an easy task and needs techniques exploiting appropriate structures of the matrices $A$ and $f(A)$ (often $f(A)$ possesses this structure only approximately). However, intermediate matrices arising during the evaluation may lose the structure of the initial matrix. This would make the computations inefficient and even infeasible. However, the main result of this paper is that an iterative fixed-point like process for the evaluation of $f(A)$ can be transformed, under certain general assumptions, into another process which preserves the convergence rate and benefits from the underlying structure. It is shown how this result applies to matrices in a tensor format with a bounded tensor rank and to the structure of the hierarchical matrix technique. We demonstrate our results by verifying all requirements in the case of the iterative computation of $A^{-1}$ and $\sqrt{A}$.
