Fast and Efficient Parallel Solution of Sparse Linear Systems

This paper presents a parallel algorithm for the solution of a linear system A x = 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(log ³ n) time and (|E| + M(s(n))) / log n processors for the evaluation of the solution vector x = A- 1 b, 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 A x = b' with the same matrix A requires only O(log ² n) time and (|E| / log n) + s(n)² processors.