On the augmented system approach to sparse least-squares problems

DOI10.1007/BF01389335zbMath0678.65024MaRDI QIDQ1124275

P. P. M. de Rijk, Mario Arioli, Iain S. Duff

Publication date: 1989

Published in: Numerische Mathematik (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/133376

zbMATH Keywords

numerical resultserror analysiscondition numberscalingnormal equationstest matricesleast-squares problemIterative refinements

Mathematics Subject Classification ID

Numerical solutions to overdetermined systems, pseudoinverses (65F20) Numerical computation of matrix norms, conditioning, scaling (65F35)

Related Items (47)

A class of modified GSS preconditioners for complex symmetric linear systems ⋮ Condition numbers and perturbation analysis for the Tikhonov regularization of discrete ill-posed problems ⋮ Enhancing Block Cimmino for Sparse Linear Systems with Dense Columns via Schur Complement ⋮ Corrected sequential linear programming for sparse minimax optimization ⋮ Solution of augmented linear systems using orthogonal factorizations ⋮ Efficient Preconditioners for Interior Point Methods via a New Schur Complement-Based Strategy ⋮ Solution of sparse rectangular systems using LSQR and Craig ⋮ A parameterized shift-splitting preconditioner for saddle point problems ⋮ A Novel Partitioning Method for Accelerating the Block Cimmino Algorithm ⋮ Symmetric SOR method for augmented systems ⋮ Semi-convergence analysis of GMSSOR methods for singular saddle point problems ⋮ Componentwise analysis of direct factorization of real symmetric and Hermitian matrices ⋮ On Using Cholesky-Based Factorizations and Regularization for Solving Rank-Deficient Sparse Linear Least-Squares Problems ⋮ A class of new extended shift-splitting preconditioners for saddle point problems ⋮ Convergence of a generalized MSSOR method for augmented systems ⋮ Convergence of relaxation iterative methods for saddle point problem ⋮ Preconditioning indefinite systems in interior point methods for large scale linear optimisation ⋮ Interior point methods 25 years later ⋮ A modified symmetric successive overrelaxation method for augmented systems ⋮ Generalized AOR method for solving a class of generalized saddle point problems ⋮ The solution of large-scale least-squares problems on supercomputers ⋮ Iterative refinement enhances the stability of \(QR\) factorization methods for solving linear equations ⋮ Selection of fictitious independent variables for the solution of sparse linear equations ⋮ On generalized symmetric SOR method for augmented systems ⋮ Variants of the Uzawa method for three-order block saddle point problem ⋮ On condition numbers for Moore–Penrose inverse and linear least squares problem involving Kronecker products ⋮ On the GTSOR-like Method for the Augmented systems ⋮ A condition analysis of the weighted linear least squares problem using dual norms ⋮ Regularization and preconditioning of KKT systems arising in nonnegative least-squares problems ⋮ Improved componentwise verified error bounds for least squares problems and underdetermined linear systems ⋮ Symmetric-triangular decomposition and its applications. II: Preconditioners for indefinite systems ⋮ Implementing cholesky factorization for interior point methods of linear programming ⋮ A survey of direct methods for sparse linear systems ⋮ A class of Uzawa-SOR methods for saddle point problems ⋮ Exploiting structure in parallel implementation of interior point methods for optimization ⋮ On the minimum convergence factor of a class of GSOR-like methods for augmented systems ⋮ Using dual techniques to derive componentwise and mixed condition numbers for a linear function of a linear least squares solution ⋮ Perturbation analysis of saddle-point problems ⋮ The augmented system variant of IPMs in two-stage stochastic linear programming computation ⋮ Perturbation bound of singular linear systems ⋮ Warm start of the primal-dual method applied in the cutting-plane scheme ⋮ The role of the augmented system in interior point methods ⋮ On mixed and componentwise condition numbers for Moore–Penrose inverse and linear least squares problems ⋮ A generalized shift-splitting preconditioner for saddle point problems ⋮ Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization ⋮ Component-wise perturbation analysis and error bounds for linear least squares solutions ⋮ Solving symmetric indefinite systems in an interior-point method for linear programming

Uses Software

• Harwell-Boeing sparse matrix collection

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides
• Jordan-Elimination und Ausgleichung nach kleinsten Quadraten
• Condition Estimates
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• On the Method of Weighting for Equality-Constrained Least-Squares Problems
• A Survey of Condition Number Estimation for Triangular Matrices
• Sparse matrix test problems
• Scaling for Numerical Stability in Gaussian Elimination
• Iterative Refinement Implies Numerical Stability for Gaussian Elimination
• Solving Sparse Linear Systems with Sparse Backward Error
• Iterative refinement of linear least squares solutions I

This page was built for publication: On the augmented system approach to sparse least-squares problems