Ordering Methods for Sparse Matrices and Vector Computers
Abstract
Direct factorization methods for solving large sparse linear equations are used as fundamental building blocks for the numerical solution of many scientific and computational problems. It is well known that reordering the variables and equations is crucial in reducing the cost of performing direct solution techniques. The problem of finding the optimal reordering is known to be an NP-complete problem. As a result, practical reordering algorithms are heuristic, and their behavior is usually only known empirically. Different reordering heuristics have been developed in a number of different disciplines, reflecting the different types of sparse linear systems and different views of the cost of computing. This research has been concerned with furthering our understanding of how ordering heuristics and their companion numerical solution routines behave on high performance computers. The availability of such computers has led to a dramatic increase in the size and complexity of scientific computations. This is the arena in which better heuristics have the largest effect on the cost of scientific computing, but it is also an arena in which architectural constraints chosen for high speed often appear to conflict with sparsity.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 31, 1988
- Accession Number
- ADA198291
Entities
People
- John G. Lewis
Organizations
- Boeing