Search

MiS Preprint Repository

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}$.

Received:
Nov 30, 2005
Published:
Nov 30, 2005
MSC Codes:
65F30, 65F50, 65F10
Keywords:
iterative algorithms, structured matrices, matrix functions, matrix approximations, low-rank matrices, hierarchical matrices, kronecker products

Related publications

inJournal
2008 Journal Open Access
Wolfgang Hackbusch, Boris N. Khoromskij and Eugene E. Tyrtyshnikov

Approximate iterations for structured matrices

In: Numerische Mathematik, 109 (2008) 3, pp. 365-383