Splitting dense columns in sparse linear systems
From MaRDI portal
Let \(A=[S,D]\) where S and D denote respectively the sparse and dense columns of a matrix A. The author gives an efficient and robust method for solving \(AA^ Tx=b.\) The proposed method avoids the rank-deficiency problem that is common to the present algorithms and also makes an effective use of sparse matrix techniques. Applications to interior-point methods for linear programming and non-symmetric matrices are pointed out.
Recommendations
- Splitting dense columns of constraint matrix in interior point methods for large scale linear programming11The results discussed in the paper have been obtained when the author was staying at LAMSADE, University of Paris Dauphine, Pl
- A product-form Cholesky factorization method for handling dense columns in interior point methods for linear programming
- A modified Schur-complement method for handling dense columns in interior-point methods for linear programming
- On the use of dense matrix techniques within sparse simplex
- Block row projection method based on M-matrix splitting
Cites work
- ALPO: Another Linear Program Optimizer
- An Implementation of a Primal-Dual Interior Point Method for Linear Programming
- An implementation of Karmarkar's algorithm for linear programming
- Computational experience with a primal-dual interior point method for linear programming
- Data Structures and Programming Techniques for the Implementation of Karmarkar's Algorithm
- Formulating Two-Stage Stochastic Programs for Interior Point Methods
- Further Development of a Primal-Dual Interior Point Method
- scientific article; zbMATH DE number 554736 (Why is no real title available?)
- Implementation of a Dual Affine Interior Point Algorithm for Linear Programming
- Implementations of Affine Scaling Methods: Approximate Solutions of Systems of Linear Equations Using Preconditioned Conjugate Gradient Methods
- On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear Programming
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- The Optimal Choice of a Subset of a Population
Cited in
(14)- Solving symmetric indefinite systems in an interior-point method for linear programming
- Matrix enlarging methods and their application
- A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows
- Block row projection method based on M-matrix splitting
- Fast Fourier optimization
- Detecting ``dense columns in interior point methods for linear programs
- Matrix stretching for sparse least squares problems
- Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods
- Splitting dense columns of constraint matrix in interior point methods for large scale linear programming11The results discussed in the paper have been obtained when the author was staying at LAMSADE, University of Paris Dauphine, Place du Marechal de Lattre de Tassigny, 75775 Paris Cedex 16, France$ef:22A preliminary version of the paper has been presented at the Applied Mathematical Programming and Modelling Symposium APMOD’91 in London, January 14-…
- Solving mixed sparse-dense linear least-squares problems by preconditioned iterative methods
- SOLVING LARGE SCALE LINEAR PROGRAMMING PROBLEMS USING AN INTERIOR POINT METHOD ON A MASSIVELY PARALLEL SIMD COMPUTER
- A Computational Study of Using Black-box QR Solvers for Large-scale Sparse-dense Linear Least Squares Problems
- Sparse Stretching for Solving Sparse-Dense Linear Least-Squares Problems
- Enhancing Block Cimmino for Sparse Linear Systems with Dense Columns via Schur Complement
This page was built for publication: Splitting dense columns in sparse linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q803727)
