We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Updating and downdating an upper trapezoidal sparse orthogonal factorization†.
- Authors
Santos-Palomo, Ángel; Guerrero-GarcÍa, Pablo
- Abstract
We describe how to update and downdate an upper trapezoidal sparse orthogonal factorization, namely the sparse QR factorization of AkT, 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 this, we have adapted Saunders' techniques of the early 1970s for square matrices, to rectangular matrices (with fewer columns than rows) by using the static data structure of George and Heath of the early 1980s but allowing row downdating on it. An implicitly determined column permutation allows 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.
- Subjects
FACTORIZATION; SPARSE matrices; ORTHOGONAL functions; ALGORITHMS; LINPACK (Computer system)
- Publication
IMA Journal of Numerical Analysis, 2006, Vol 26, Issue 1, p1
- ISSN
0272-4979
- Publication type
Article
- DOI
10.1093/imanum/dri027