Updating a Rank-Revealing ULV Decomposition

A ULV decomposition of a matrix A of order n is a decomposition of the form A = ULVH, where U and V are orthogonal matrices and L is a lower triangular matrix. When A is approximately of rank k, the decomposition is rank revealing if the last $n - k$ rows of L are small. This paper presents algorithms for updating a rank-revealing ULV decomposition. The algorithms run in O( n² ) time, and can be implemented on a linear array of processors to run in $O( n )$ time.