Interactive Educational Modules in
Scientific Computing

QR Factorization with Column Pivoting

This module illustrates Householder QR factorization with column pivoting. The initial matrix is reduced to upper triangular form by applying a sequence of Householder transformations to annihilate the subdiagonal entries in successive columns, but the columns are not necessarily processed in their original order in the matrix. For example, to select a maximum independent set of columns, the next column selected for reduction at each stage should be the column of the remaining unreduced matrix having maximum norm.

The user first selects a matrix size, then selects a matrix by choosing a preset example, a random matrix, or typing in desired entries. The successive steps of Householder QR factorization with column pivoting are then carried out sequentially by repeatedly clicking on NEXT or on the currently highlighted step. The next column to be reduced is selected by clicking on it; a default choice (the unreduced column having largest norm) is highlighted in color. The selected column is interchanged with the leading unreduced column of the matrix. A Householder transformation is then determined that annihilates the subdiagonal entries of the current column. The corresponding Householder vector v is displayed on the right, and the computed values of the scalars α and β are shown in text boxes. The Householder transformation is also applied to the remaining unreduced columns of the matrix. The factorization process is complete when the original matrix has been reduced to upper triangular form. Formats provided for displaying numeric entries include exponential (e), fixed (f), and generic (g), with g the default.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 3.5.4.

Developers: Jessica Schoen and Michael Heath