Approximate Iterations for Structured Matrices

Wolfgang Hackbusch, Boris N. Khoromskij, and Eugene E. Tyrtyshnikov

Contact the author: Please use for correspondence this email.
Submission date: 30. Nov. 2005 (revised version: March 2007)
Pages: 16
published in: Numerische Mathematik, 109 (2008) 3, p. 365-383 
DOI number (of the published article): 10.1007/s00211-008-0143-0
Bibtex
MSC-Numbers: 65F30, 65F50, 65F10
Keywords and phrases: iterative algorithms, structured matrices, matrix functions, matrix approximations, low-rank matrices, hierarchical matrices, kronecker products
Download full preprint: PDF (262 kB), PS ziped (259 kB)

Abstract:
Important matrix-valued functions f(A) are, e.g., the inverse , the square root , 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 and .