Maintaining LU factors of a general sparse matrix

DOI10.1016/0024-3795(87)90112-1zbMath0618.65019OpenAlexW2081387733MaRDI QIDQ1822448

Margaret H. Wright, Michael A. Saunders, Philip E. Gill, Walter Murray

Publication date: 1987

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(87)90112-1

zbMATH Keywords

error analysisLU factorizationsparse matrix factorizationpivotal strategyrank one modificationstorage methodsupdating LU factors

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Factorization of matrices (15A23) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (22)

Structural conserved moiety splitting of a stoichiometric matrix ⋮ A Technique for Updating Hierarchical Skeletonization-Based Factorizations of Integral Operators ⋮ Solving Multiscale Linear Programs Using the Simplex Method in Quadruple Precision ⋮ The implementation of linear programming algorithms based on homotopies ⋮ Model-predictive control of a combined sewer system ⋮ Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates ⋮ Stable algorithm for updating denseLUfactorization after row or column exchange and row and column addition or deletion ⋮ A structured modified Newton approach for solving systems of nonlinear equations arising in interior-point methods for quadratic programming ⋮ Fast Factorization Update for General Elliptic Equations Under Multiple Coefficient Updates ⋮ An efficient algorithm for sparse null space basis problem using ABS methods ⋮ An efficient approach to updating simplex multipliers in the simplex algorithm ⋮ qpOASES: a parametric active-set algorithm for~quadratic programming ⋮ Extension of GAMS for complementarity problems arising in applied economic analysis ⋮ Crashing a maximum-weight complementary basis ⋮ A primal deficient-basis simplex algorithm for linear programming ⋮ On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method ⋮ An efficient method for nonlinearly constrained networks ⋮ A preconditioner for solving large-scale variational inequality problems by a semismooth inexact approach ⋮ Conjectures and Computations about Veronese Syzygies ⋮ Sensitivity method for basis inverse representation in multistage stochastic linear programming problems ⋮ A reduced proximal-point homotopy method for large-scale non-convex BQP ⋮ Methods for convex and general quadratic programming

Uses Software

• MINOS
• MA28

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Direct methods for sparse matrices
• Rank and null space calculations using matrix decomposition without column interchanges
• An extension of Karmarkar's algorithm for linear programming using dual variables
• Y12M. Solution of large and sparse systems of linear algebraic equations. Documentation of subroutines
• A stabilization of the simplex method
• The Elimination form of the Inverse and its Application to Linear Programming
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• Analysis of Pairwise Pivoting in Gaussian Elimination
• Inertia-Controlling Methods for General Quadratic Programming
• A Structurally Stable Modification of Hellerman–Rarick’s ${\text{P}}^4 $ Algorithm for Reordering Unsymmetric Sparse Matrices
• On Some Pivotal Strategies in Gaussian Elimination by Sparse Technique
• A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases
• Algorithms for sparse Gaussian elimination with partial pivoting
• Sparse Matrix Methods in Optimization
• The simplex method of linear programming using LU decomposition
• The least squares problem and pseudo-inverses
• A Note on the Stability of Gaussian Elimination
• The Solution of Large Sparse Unsymmetric Systems of Linear Equations
• Reinversion with the preassigned pivot procedure

This page was built for publication: Maintaining LU factors of a general sparse matrix