Minimizing Fill-In for Gaussian Elimination of Symmetric Systems.
Abstract
The new projective linear programming algorithm by Karmarkar requires solution of symmetric, positive definite systems of equations. One key to solving these systems efficiently is minimizing the fill-in; i.e., the number of new nonzero elements in the reduced matrix, in the various forms of Gaussian elimination used to solve these systems. Fill-in is affected only by symmetric reordering of rows and columns of the system of equations. Various heuristic ordering algorithms are tested and compared with the heuristic minimum degree algorithm of George and Liu. Computational results are reported for sixteen large-scale real-world and artificial problems. The minimum degree algorithm of George and Liu is the most effective of six tested methods. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1985
- Accession Number
- ADA161196
Entities
People
- Young H. Seo
Organizations
- Naval Postgraduate School