Fast and efficient parallel solution of sparse linear systems

This paper presents a parallel algorithm for the solution of a linear system Ax = b with a sparse n × n symmetric positive definite matrix A, associated with the graph G(A) that has n vertices and has an edge for each nonzero entry of A. If G(A) has an s(n)-separator family and a known s(n)-separator tree, then the algorithm requires only O(log3 n) time and (|E| + M(s(n)))/log n processors for the evaluation of the solution vector x = A-1b, where |E| is the number of edges in G(A) and M(n) is the number of processors sufficient for multiplying two n × n rational matrices in time O(log n). Furthermore, for this computational cost the algorithm computes a recursive factorization of A such that the solution of any other linear system Ax = b′ with the same matrix A requires only O(log2n) time and (|E| log n) + s(n)2 processors.

Duke Scholars

Author John H. Reif Computer Science