Publications [#237087] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Pan, V; Reif, J, EFFICIENT PARALLEL SOLUTION OF LINEAR SYSTEMS., Conference Proceedings of the Annual ACM Symposium on Theory of Computing (January, 1985), pp. 143-152, ACM Press, New York (Presented at the meeting on Efficient Algorithms, Mathematisches Forschungsinstitut, Oberwolfach, W. Germany, November 1984. Presented at 2nd SIAM Conference on Applied Linear Algebra, Raleigh, NC, April 1985.) [pdf], [doi]
   (last updated on 2026/01/16)

   Abstract:
   This paper describes parallel algorithms that have good numerical stability and remain efficient as n grows large. In particular, we describe a quadratically convergent iterative method that gives the inverse of an n multiplied by n rational matrix A with condition less than equivalent to n**O**(**1**) in O(log n)**2 time using M(n) processors. This is the optimum processor bound and the factor n**0**. **5 improvement of known processor bounds for polylog time matrix inversion. It is the first known polylog time algorithm that is numerically stable. The algorithm relies on our method of computing an approximate inverse of A that involves O(log n) parallel steps and n**2 processors. Also, we give a parallel algorithm for solution of a linear system Ax equals b with a sparse n multiplied by n symmetric positive definite matrix A.