A Structurally Stable Modification of Hellerman–Rarick’s ${\text{P}}^4 $ Algorithm for Reordering Unsymmetric Sparse Matrices

The Partitioned Preassigned Pivot Procedure $({\text{P}}^4 )$ of Hellerman and Rarick reorders unsymmetric sparse matrices in order to decrease computation and storage requirements when solving sparse systems of linear equations. It is known that the algorithm, when applied to matrices that are not...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on numerical analysis 1985-04, Vol.22 (2), p.369-385
Main Authors: Erisman, A. M., Grimes, R. G., Lewis, J. G., Poole, Jr, W. G.
Format: Article
Language:English
Subjects:
Algorithms
Linear programming
Sparsity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The Partitioned Preassigned Pivot Procedure $({\text{P}}^4 )$ of Hellerman and Rarick reorders unsymmetric sparse matrices in order to decrease computation and storage requirements when solving sparse systems of linear equations. It is known that the algorithm, when applied to matrices that are not structurally singular, can generate intermediate matrices that are structurally singular, causing a breakdown in the elimination process. In this paper we present the algorithm in a structured, top-down, form and explain several of the problems that may occur. We then define a modification of the algorithm that avoids these difficulties. The revised version of the algorithm will never produce structurally singular intermediate matrices if the original matrix is not structurally singular. Test results with this modified algorithm show that it is as effective as the Markowitz algorithm as a preordering when the block structure of the new algorithm is recognized and used.
ISSN:0036-1429
1095-7170
DOI:10.1137/0722022