Please use this identifier to cite or link to this item:
Main Title: Orthogonal Hessenberg reduction and orthogonal Krylov subspace bases
Author(s): Liesen, Jörg
Saylor, Paul E.
Type: Article
Language Code: en
Abstract: We study necessary and sufficient conditions that a nonsingular matrix A can be B-orthogonally reduced to upper Hessenberg form with small bandwidth. By this we mean the existence of a decomposition AV=VH, where H is upper Hessenberg with few nonzero bands, and the columns of V are orthogonal in an inner product generated by a hermitian positive definite matrix B. The classical example for such a decomposition is the matrix tridiagonalization performed by the hermitian Lanczos algorithm, also called the orthogonal reduction to tridiagonal form. Does there exist such a decomposition when A is nonhermitian? In this paper we completely answer this question. The related (but not equivalent) question of necessary and sufficient conditions on A for the existence of short-term recurrences for computing B-orthogonal Krylov subspace bases was completely answered by the fundamental theorem of Faber and Manteuffel [SIAM J. Numer. Anal.}, 21 (1984), pp. 352--362]. We give a detailed analysis of B-normality, the central condition in both the Faber--Manteuffel theorem and our main theorem, and show how the two theorems are related. Our approach uses only elementary linear algebra tools. We thereby provide new insights into the principles behind Krylov subspace methods, that are not provided when more sophisticated tools are employed.
Issue Date: 2006
Date Available: 20-Dec-2017
DDC Class: 518 Numerische Analysis
512 Algebra
Subject(s): linear systems
Krylov subspace methods
Hessenberg reduction
matrix decomposition
short-term recurrences
normal matrices
Journal Title: SIAM Journal on Numerical Analysis
Publisher: Society for Industrial and Applied Mathematics
Publisher Place: Philadelphia, Pa
Volume: 42
Issue: 5
Publisher DOI: 10.1137/S0036142903393372
Page Start: 2148
Page End: 2158
EISSN: 1095-7170
ISSN: 0036-1429
Appears in Collections:FG Numerische Lineare Algebra » Publications

Files in This Item:
File Description SizeFormat 
2006_Liesen_et-al.pdf136.8 kBAdobe PDFThumbnail

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