EFFICIENT PARALLEL SOLUTION OF LINEAR SYSTEMS.

Published

Journal Article

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.

Duke Authors

Cited Authors

  • Pan, V; Reif, J

Published Date

  • January 1, 1985

Published In

Start / End Page

  • 143 - 152

International Standard Serial Number (ISSN)

  • 0734-9025

Citation Source

  • Scopus