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

Abstract

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1983
Accession Number
ADA129344

Entities

People

  • A. M. Erisman
  • J. G. Lewis
  • R. G. Grimes
  • W. G. Poole Jr.

Organizations

  • Boeing

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algebra
  • Algorithms
  • Application Software
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computers
  • Elimination
  • Equations
  • Information Science
  • Linear Algebra
  • Linear Programming
  • Mathematics
  • Permutations
  • Scientific Research
  • Sparse Matrix

Readers

  • Linear Algebra
  • Operations Research