Updating and downdating an upper trapezoidal sparse orthogonal factorization†
Ángel Santos-Palomo, Pablo Guerrero-Garcı́a · IMA Journal of Numerical Analysis · 2005
We describe how to update and downdate an upper trapezoidal sparse orthogonal factorization, namely the sparse QR factorization of AT k, where Ak is a “tall and thin” full column rank matrix formed with a subset of the columns of a fixed matrix A. In order to do that, we have adapted to rectangular matrices (with fewer columns than rows) Saunders’ techniques of early 70s for square matrices, by using the static data structure of George and Heath of early 80s but allowing row downdating on it. An implicitly determined column permutation allow us to dispense with computing a new ordering after each update/downdate; it fits well into the Linpack downdating algorithm and ensures that the updated trapezoidal factor will remain sparse. We give all the necessary formulae even if the orthogonal factor is not available, and we comment on our implementation using the sparse toolbox of Matlab 5.