A sparse counterpart of Reichel and Gragg's package QRUP

DOI10.1016/J.CAM.2007.04.051MaRDI QIDQ1044853zbMATH OpenOpenAlexFDO

Authors Pablo Guerrero-García, Ángel Santos-Palomo

Publication date 15 December 2009

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cam.2007.04.051

zbMATH Keywords

\texttt{Matlab}Givens' rotationssparse orthogonalizationsparse QR factorization

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Computational methods for sparse matrices (65F50)

Review text

The authors deal with the problem of maintaining the triangular factor of a sparse QR factorization when columns are added and deleted and \(Q\) cannot be stored for sparsity reasons. In this respect they adapt the sparse direct methodology of \textit{Å. Björck} [Numer. Math. 54, No.~1, 19--32 (1988; Zbl 0659.65039)] and \textit{U. Oreborn} [A direct method for sparse nonnegative least squares problems, Lic. Thesis, Dept. Math., Linköping Univ. (1986)], without formatting \(A^T A\). The \texttt{Matlab} implementations presented in the paper use a suitable row and column numbering within a static triangular sparsity computed in advance.

Recommendations

• Updating and downdating an upper trapezoidal sparse orthogonal factorization†
• A software package for sparse orthogonal factorization and updating
• Sparse QR factorization in MATLAB
• Multiple-rank modifications of a sparse Cholesky factorization
• Maintaining LU factors of a general sparse matrix

Cites work

• A direct active set algorithm for large sparse quadratic programs with simple bounds
• A direct method for sparse least squares problems with lower and upper bounds
• A numerically stable form of the simplex algorithm
• A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases
• Active set algorithms for isotonic regression; a unifying framework
• Algorithm 686: FORTRAN subroutines for updating the QR decomposition
• scientific article; zbMATH DE number 3784219 (Why is no real title available?)
• scientific article; zbMATH DE number 852536 (Why is no real title available?)
• scientific article; zbMATH DE number 883145 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Newton's Method for Large Bound-Constrained Optimization Problems
• On the Convergence of a Class of Infeasible Interior-Point Methods for the Horizontal Linear Complementarity Problem
• On the Use of Structural Zeros in Orthogonal Factorization
• Row Modifications of a Sparse Cholesky Factorization
• Sparse Matrices in MATLAB: Design and Implementation
• Updated triangular factors of the basis to maintain sparsity in the product form simplex method

Cited in

(3)

• QRUP
• Updating and downdating an upper trapezoidal sparse orthogonal factorization†
• A software package for sparse orthogonal factorization and updating

Describes a project that uses

Uses Software

• Matlab
• TOMS-686
• TRON
• symrcm

This page was built for publication: A sparse counterpart of Reichel and Gragg's package QRUP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1044853)