Tridiagonalization of a Symmetric MatrixIf A is a real symmetric n×n matrix, then A is orthogonally similar to a real tridiagonal n×n matrix T, i.e. there exists an orthogonal matrix U such that UT A U = T.
A Householder transformation is an orthogonal transformation of the form
Q = I - 2 u uT / uT u, where u is a column vector. The algorithm programmed below starts with the last row, calculates the Householder transformation which annihilates all elements to the left of the subdiagonal. The algorithm then continues up the matrix by calculating the Householder transformation which annihilates all elements to the left of the subdiagonal for that row and leaves invariant the previously selected rows.
- int Tridiagonalize_Symmetric_Matrix(double *A, int storage_class, double diagonal[ ], double off_diagonal[ ], double *U, int n)
Given the n×n symmetric matrix A, the routine Tridiagonalize_Symmetric_Matrix transforms A to a tridiagonal symmetric matrix by a sequence of Householder transformations. The diagonal of the resulting tridiagonal matrix is returned in the array diagonal and the off-diagonal is returned in the array off_diagonal starting at off_diagonal (off_diagonal is set to 0.0). The transformation matrix, U, where A U = U T, and T is the tridiagonal matrix with diagonal, diagonal, and off-diagonal, off_diagonal, is returned in the array U. The input parameter storage_class refers to the manner in which the input matrix A is stored. If A is stored as a full symmetric matrix, storage_class should be set to 0, if A is stored in lower triangular form, storage_class should be set to -1, and if A is stored in upper triangular form, storage_class should be set to 1. The arrays diagonal and off_diagonal should be dimensioned at least n in the calling routine. The matrix U should be dimensioned at least n². The matrix A is preserved.
The function returns 0 if it is successful and -1 if storage_class is illegal.
C Source Code
- The file, tridiagonalize_symmetric_matrix.c, contains the routine Tridiagonalize_Symmetric_Matrix( ).