# 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