Publications [#236961] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Pan, V; Reif, J, Fast and efficient parallel solution of sparse linear systems, SIAM Journal on Computing, vol. 22 no. 6 (January, 1993), pp. 1227-1250, Society for Industrial & Applied Mathematics (SIAM) [doi]
   (last updated on 2026/01/14)

   Abstract:
   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(log³ 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(log²n) time and (|E| log n) + s(n)² processors.