Accession Number : ADA267144


Title :   Decomposition of Large Sparse Symmetric Systems for Parallel Computation. Part 1. Theoretical Foundations


Descriptive Note : Final rept.,


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


Personal Author(s) : Kevorkian, A K


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a267144.pdf


Report Date : Mar 1993


Pagination or Media Count : 62


Abstract : Given a sparse symmetric matrix M, we develop a linear-time algorithm to construct in the undirected graph G = (V, E) of M a vertex partition II* = (V1, V2, ..., Vr, S*) satisfying the following three properties. First, for any two distinct elements Vi and Vj of the partition, no vertex in Vi is adjacent to a vertex in Vj. Second, every element Vi of the partition induces a clique in G. Third, if A is a full principal submatrix of M such that the symbolic factorization of A does not produce fill-in, then the set of vertices in G corresponding to the rows of A is a subset of an element Vi of the partition. By the first two properties of the vertex partition II*, the solution of a sparse symmetric problem is reduced to the solution of smaller dense symmetric subproblems. In the case where M is a positive definite matrix, the first property allows us to factorize r dense symmetric blocks in parallel as well as solve in parallel r triangular systems with multiple right-hand sides. The third property is a means for computing an ordering that produces acceptably small fill-in.... Cliques, Fill-in, Parallel computation, Separators, Simplicial vertices, Symbolic factorization


Descriptors :   *COMPUTATIONS , *PARALLEL PROCESSING , *SPARSE MATRIX , ALGORITHMS , TIME , OCEAN SURVEILLANCE , SEPARATORS , DECOMPOSITION , COMMAND AND CONTROL SYSTEMS , GRAPHS , COMPUTER ARCHITECTURE


Subject Categories : Numerical Mathematics


Distribution Statement : APPROVED FOR PUBLIC RELEASE