Accession Number : ADA299387

Title :   An Ordering Algorithm for Exposing Parallelism in Sparse Symmetric Matrices.

Descriptive Note : Final rept.,

Corporate Author : NAVAL COMMAND CONTROL AND OCEAN SURVEILLANCE CENTER RDT AND E DIV SAN DIEGO CA

Personal Author(s) : Kevorkian, Aram K.

PDF Url : ADA299387

Report Date : MAY 1995

Pagination or Media Count : 34

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)

Descriptors :   *ALGORITHMS, *SPARSE MATRIX, OPTIMIZATION, COMPUTATIONS, MATRICES(MATHEMATICS), LINEAR PROGRAMMING, PARALLEL PROCESSING, SYMMETRY, NUMERICAL METHODS AND PROCEDURES, APPLIED MATHEMATICS, ITERATIONS.

Subject Categories : Numerical Mathematics
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE