Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-6560
Main Title: On optimal short recurrences for generating orthogonal Krylov subspace bases
Author(s): Liesen, Jörg
Strakoš, Zdenek
Type: Article
Language Code: en
Abstract: We analyze necessary and sufficient conditions on a nonsingular matrix A such that, for any initial vector $r_0$, an orthogonal basis of the Krylov subspaces ${\cal K}_n(A,r_0)$ is generated by a short recurrence. Orthogonality here is meant with respect to some unspecified positive definite inner product. This question is closely related to the question of existence of optimal Krylov subspace solvers for linear algebraic systems, where optimal means the smallest possible error in the norm induced by the given inner product. The conditions on A we deal with were first derived and characterized more than 20 years ago by Faber and Manteuffel (SIAM J. Numer. Anal., 21 (1984), pp. 352–362). Their main theorem is often quoted and appears to be widely known. Its details and underlying concepts, however, are quite intricate, with some subtleties not covered in the literature we are aware of. Our paper aims to present and clarify the existing important results in the context of the Faber–Manteuffel theorem. Furthermore, we review attempts to find an easier proof of the theorem and explain what remains to be done in order to complete that task.
URI: https://depositonce.tu-berlin.de//handle/11303/7287
http://dx.doi.org/10.14279/depositonce-6560
Issue Date: 5-Aug-2008
Date Available: 19-Dec-2017
DDC Class: DDC::500 Naturwissenschaften und Mathematik::510 Mathematik::518 Numerische Analysis
DDC::500 Naturwissenschaften und Mathematik::510 Mathematik::512 Algebra
Subject(s): Krylov subspace methods
orthogonal bases
short recurrences
conjugate gradient-like methods
Usage rights: Terms of German Copyright Law
Journal Title: SIAM Review
Publisher: Society for Industrial and Applied Mathematics
Publisher Place: Philadelphia, Pa
Volume: 50
Issue: 3
Publisher DOI: 10.1137/060662149
Page Start: 485
Page End: 503
EISSN: 1095-7200
ISSN: 0036-1445
Appears in Collections:Fachgebiet Numerische Lineare Algebra » Publications

Files in This Item:
File Description SizeFormat 
2008_Liesen_et-al.pdf493.19 kBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.