Efficient Parallel Solution of Linear Systems

The most efficient known parallel algorithms for inversion of a nonsingular n × n matrix A or solving a linear system Ax = b over the rationals require Ο(log n) 2 time and M(n)n 0.5 processors (where M(n) is the number of processors required in order to multiply two n × n rational matrices in time Ο(log n).) Furthermore, all known polylog time algorithms for those problems are unstable : they require the calculation to be done with perfect precision; otherwise they give no results at all.

Authors

• Victor Y. Pan
• John H. Reif

Keywords

No keywords are indexed for this paper.