Interactive Educational Modules in
Scientific Computing

Orthogonal Reduction to Hessenberg Form

This module illustrates the reduction of a matrix A to Hessenberg form by a similarity transformation A = Q H QT, where matrix H is upper Hessenberg, meaning that all of its entries below the first subdiagonal are zero, and Q is an orthogonal matrix. Similarity reduction to this form is a preliminary step toward computing the eigenvalues and eigenvectors of A using QR iteration, and is accomplished by applying a sequence of Householder transformations to annihilate selected matrix entries in successive columns. An orthogonal similarity transformation preserves symmetry, so if the initial matrix A is symmetric, then the resulting matrix is tridiagonal, in which case it is often denoted by T rather than H.

The user first selects a matrix size and whether the matrix is to be symmetric, then selects a specific matrix by choosing a preset example, a random matrix, or typing in desired entries. The successive steps of Hessenberg reduction are then carried out sequentially by repeatedly clicking on NEXT or on the currently highlighted step. The current column is indicated by an arrow. For each successive column, a Householder transformation is determined that annihilates the entries of the given column below the first subdiagonal. The corresponding Householder vector is displayed on the right, and the computed values of associated scalars are shown in text boxes. The Householder transformation is applied from the left to the columns of the matrix. To attain a similarity transformation, the Householder transformation is also applied from the right to the rows of the matrix. Note that the latter process does not affect any zero entries previously introduced into the matrix. The reduction process is complete when the original matrix has been reduced to upper Hessenberg form, or tridiagonal form if the initial matrix is symmetric. Formats provided for displaying numeric entries include exponential (e), fixed (f), and generic (g), with g the default.

References:

  1. Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Sections 3.5.1 and 4.5.6.

  2. Lloyd N. Trefethen and David Bau, Numerical Linear Algebra, SIAM, Philadelphia, 1997. See Lecture 26.

Developers: Jing Zou and Michael Heath