Incremental Condition Calculation and Column Selection
G. W. Stewart · University Libraries (University of Maryland) · 1998
This paper describes a method for calculating the condition number of a matrix in the Frobenius norm that can be used to select columns in the course of computing a QR decomposition. When the number of rows of the matrix is much greater than the number of columns, the additional overhead is negligible. Limited numerical experiments suggest that the method is quite good at finding gaps in the singular values of the matrix. 1. Introduction The problem of condition estimation is to approximate the norm of an inverse or pseudo-inverse of a matrix. The matrix is typically a triangular matrix R --- often the result of computing a QR or LR factorization. The first condition estimator was devised by Gragg and Stewart [8], and was later improved by Cline, Moler, Stewart, and Wilkinson [4] for incorporation into linpack [5]. Other condition estimators have since been proposed, many of which are treated in a survey by Higham [9]. Condition estimators typically trade precision for speed. They pr...