Fast and efficient parallel solution of dense linear systems

Published

Journal Article

The most efficient previously known parallel algorithms for the inversion of a nonsingular n × n matrix A or solving a linear system Ax = b over the rational numbers require O(log2n) time and M(n) n processors [provided that M(n) processors suffice in order to multiply two n × n rational matrices in time O(logn)]. Furthermore, the known polylog arithmetic time algorithms for those problems are numerically unstable. In this paper we apply Newton's iteration and initially choose an approximate inverse matrix by following Ben-Israel. This quadratically convergent and numerically stable iterative method takes O(log2n) parallel time using M(n) processors to compute the inverse (within the relative precision 2-nc for a positive constant c) of an n × n rational matrix A with the condition number at most nd for a constant d. This is the optimum processor bound and by a factor of n improvement of the previously known processor bounds for polylogarithmic time matrix inversion. The algorithm does not require to precompute the condition number of the input matrix, but it just converges slower for ill-conditioned input matrices. © 1989.

Full Text

Duke Authors

Cited Authors

  • Pan, V; Reif, J

Published Date

  • January 1, 1989

Published In

Volume / Issue

  • 17 / 11

Start / End Page

  • 1481 - 1491

International Standard Serial Number (ISSN)

  • 0898-1221

Digital Object Identifier (DOI)

  • 10.1016/0898-1221(89)90081-3

Citation Source

  • Scopus