Abstract
Numerous algorithms in numerical linear algebra are based on the reduction of a given matrix A to a more convenient form. One of the most useful types of such reduction is the orthogonal reduction to (upper) Hessenberg form. This reduction can be computed by the Arnoldi algorithm. When A is Hermitian, the resulting upper Hessenberg matrix is tridiagonal, which is a significant computational advantage. In this paper we study necessary and sufficient conditions on A so that the orthogonal Hessenberg reduction yields a Hessenberg matrix with small bandwidth. This includes the orthogonal reduction to tridiagonal form as a special case. Orthogonality here is meant with respect to some given but unspecified inner product. While the main result is already implied by the Faber-Manteuffel theorem on short recurrences for orthogonalizing Krylov sequences (see Liesen and Strakoš, SIAM Rev 50:485–503, 2008), we consider it useful to present a new, less technical proof. Our proof utilizes the idea of a “minimal counterexample”, which is standard in combinatorial optimization, but rarely used in the context of linear algebra.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arnoldi, W.E.: The principle of minimized iteration in the solution of the matrix eigenvalue problem. Q. Appl. Math. 9, 17–29 (1951)
Faber, V., Liesen, J., Tichý, P.: The Faber-Manteuffel theorem for linear operators. SIAM J. Numer. Anal. 46, 1323–1337 (2008)
Faber V., Manteuffel, T.: Necessary and sufficient conditions for the existence of a conjugate gradient method. SIAM J. Numer. Anal. 21, 352–362 (1984)
Huckle, T.: The Arnoldi method for normal matrices. SIAM J. Matrix Anal. Appl. 15, 479–489 (1994)
Lanczos, C.: An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Natl. Bur. Stand. 45, 255–282 (1950)
Liesen, J., Saylor, P.E.: Orthogonal Hessenberg reduction and orthogonal Krylov subspace bases. SIAM J. Numer. Anal. 42, 2148–2158 (2005)
Liesen, J., Strakoš, Z.: On optimal short recurrences for generating orthogonal krylov subspace bases. SIAM Rev. 50, 485–503 (2008)
Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia (2003)
Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 7, 856–869 (1986)
Watkins, D.S.: The QR algorithm revisited. SIAM Rev. 50, 133–145 (2008)
Zha, H., Zhang, Z.: The Arnoldi process, short recursions, and displacement ranks. Linear Algebra Appl. 249, 169–188 (1996)
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of J. Liesen was supported by the Emmy Noether- and the Heisenberg-Program of the Deutsche Forschungsgemeinschaft.
The work of P. Tichý was supported by the Emmy Noether-Program of the Deutsche Forschungsgemeinschaft and by the GAAS grant IAA100300802.
Rights and permissions
About this article
Cite this article
Faber, V., Liesen, J. & Tichý, P. On orthogonal reduction to Hessenberg form with small bandwidth. Numer Algor 51, 133–142 (2009). https://doi.org/10.1007/s11075-008-9242-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-008-9242-3