Updating and downdating an upper trapezoidal sparse orthogonal factorization{dagger}

^** Email: santos{at}ctima.uma.es^*** Corresponding Author. Email: pablito{at}ctima.uma.es We describe how to update and downdate an upper trapezoidalsparse orthogonal factorization, namely the sparse QR factorizationof A_k^T, where A_k is a ‘tall and thin’ full columnrank matrix formed with a subset of the columns of a fixed matrixA. In order to do this, we have adapted Saunders' techniquesof the early 1970s for square matrices, to rectangular matrices(with fewer columns than rows) by using the static data structureof George and Heath of the early 1980s but allowing row downdatingon it. An implicitly determined column permutation allows usto dispense with computing a new ordering after each update/downdate;it fits well into the LINPACK downdating algorithm and ensuresthat the updated trapezoidal factor will remain sparse. We giveall the necessary formulae even if the orthogonal factor isnot available, and we comment on our implementation using thesparse toolbox of MATLAB 5.