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

摘要

Given a sparse symmetric matrix M, we develop a linear-time algorithm toconstruct 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.