Structurally Stable Modification of Hellerman-Rarick's P4 Algorithm for Reordering Unsymmetric Sparse Matrices

摘要

The Partitioned Preassigned Pivot Procedure 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 which are not structurally singular, can generate intermediate matrices which are structurally singular, causing a breakdown in the elimination process. In this paper its authors present the algorithm in a structured, top-down, form and explain several of the problems which may occur. We then define a modification of the algorithm to treat the difficulties. This 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. (Author)