SPARSE-QR
Sparse QR factorization in MATLAB In the recently presented sparse matrix extension of MATLAB, there is no routine for sparse QR factorization. Sparse linear least squares problems are instead solved by the augmented system method. The accuracy in computed solutions is strongly dependent on a scaling parameter δ. Its optimal value is expensive to compute, and it must therefore be approximated by a simple heuristic. We describe a multifrontal method for sparse QR factorization and its implementation in MATLAB. It is well known that the multifrontal approach is suitable for vector machines. We show that it is also attractive in MATLAB. In both cases, scalar operations are expensive, and the reformulation of the sparse problem into dense subproblems is advantageous. Using the new routine, we implement two methods for the solution of sparse linear least squares problems and compare these with the built-in MATLAB function. We show that the QR-based methods normally are much faster and more accurate than the MATLAB implementation of the augmented system method. A better choice of the parameter δ or iterative refinement must be used to make the augmented system method as accurate as the methods based on QR factorization.
(Source: http://plato.asu.edu)
This software is also peer reviewed by journal TOMS.
This software is also peer reviewed by journal TOMS.
Keywords for this software
References in zbMATH (referenced in 17 articles , 1 standard article )
Showing results 1 to 17 of 17.
Sorted by year (- Khorramizadeh, M.; Mahdavi-Amiri, N.: An efficient algorithm for sparse null space basis problem using ABS methods (2013)
- Gonzalez-Lima, Maria; Wei, Hua; Wolkowicz, Henry: A stable primal-dual approach for linear programming under nondegeneracy assumptions (2009)
- Le Borne, Sabine: Block computation and representation of a sparse nullspace basis of a rectangular matrix (2008)
- Le Borne, S.; Cook, D. II: Construction of a discrete divergence-free basis through orthogonal factorization in $\mathcalH$-arithmetic (2007)
- Dellaert, Frank; Kaess, Michael: Square root SAM: simultaneous localization and mapping via square root information smoothing (2006)
- Davis, Timothy A.: A column pre-ordering strategy for the unsymmetric-pattern multifrontal method (2004)
- Wolkowicz, Henry: Solving semidefinite programs using preconditioned conjugate gradients (2004)
- Malard, Joël M.: Parallel restricted maximum likelihood estimation for linear models with a dense exogenous matrix (2002)
- Daydeé, Michel J.; Décamps, Jér^ome P.; Gould, Nicholas I.M.: Subspace-by-subspace preconditioners for structured linear systems (1999)
- Golub, Gene H.; Wathen, Andrew J.: An iteration for indefinite systems and its application to the Navier-Stokes equations (1998)
- Davis, Timothy A.; Duff, Iain S.: An unsymmetric-pattern multifrontal method for sparse LU factorization (1997)
- Duff, Iain S.: Sparse numerical linear algebra: Direct methods and preconditioning (1997)
- Matstoms, Pontus: Sparse linear least squares problems in optimization (1997)
- Neumaier, Arnold: Molecular modeling of proteins and mathematical prediction of protein structure (1997)
- Matstoms, Pontus: Parallel sparse QR factorization on shared memory architectures (1995)
- Saunders, Michael A.: Solution of sparse rectangular systems using LSQR and Craig (1995)
- Matstoms, P.: Sparse QR factorization in MATLAB (1994)