An Ordering Algorithm for Exposing Parallelism in Sparse Symmetric Matrices.
Abstract
Given a sparse symmetric matrix M, we develop an ordering algorithm to find a permutation matrix P so that parallelism inherent in M is fully exposed in the matrix PMP(t). The key steps in the ordering algorithm are as follows. First, compute in the undirected graph G = (V, E) of M a set of vertices S* such that the induced subgraph G(V - S*) contains parallel regions inherent in M. This step gives rise to a block diagonal matrix A such that each diagonal block is a full matrix in M. Second, factor block diagonal matrix A symbolically and compute the symbolic form of the Schur complement of A in M. Third, replace original matrix M by the symbolic Schur complement, and repeat the process until the symbolic Schur complement is a full matrix. By a property of the set S*, the ordering algorithm takes advantage of all principal submatrices of M that do not produce fill-in in any part of M when symbolically factored. Applications to a large collection of sparse matrices show that the new ordering algorithm is an effective tool for exposing parallelism in sparse symmetric problems. Also, comparisons show that the new algorithm fares favorably with commonly used ordering methods. (AN)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1995
- Accession Number
- ADA299387
Entities
People
- Aram K. Kevorkian
Organizations
- Naval Command, Control and Ocean Surveillance Center