Sparse Gaussian Elimination of Staircase Linear Systems.
Abstract
A square system of linear equations is said to be sparse if it can be solved most efficiently through a knowledge of its arrangement of zero and nonzero coefficients. Sparse systems are commonly solved by the techniques of sparse Gaussian elimination. An important class of sparse systems are those that have a 'staircase' structure: their variables fall into a natural sequence of disjoint groups, and each equation relates only variables within the group or within two adjacent groups. This paper proposes special methods of sparse Gaussian elimination for staircase-structured systems. These methods are particularly applicable to linear programming problems whose constraints have a staircase structure; they may also find application in solving staircase linear systems that arise in nonlinear optimization and optimal control. The initial sections of this paper present a self-contained review of sparse elimination, and derive pertinent properties of staircase systems. Subsequent sections pursue two approaches to staircase elimination, and report initial computational experience in detail. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1979
- Accession Number
- ADA081856
Entities
People
- Robert Fourer
Organizations
- Stanford University