Search

MiS Preprint Repository

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
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