Parallel Complexity of Numerically Accurate Linear System Solvers

TitleParallel Complexity of Numerically Accurate Linear System Solvers
Publication TypeTechnical Report
Year of Publication1997
AuthorsLeoncini, M., Manzini G., & Margara L.
Other Numbers1097

We prove a number of negative results about practical (i.e., work efficient and numerically accurate) algorithms for computing the main matrix factorizations. In particular, we prove that the popular Householder and Givens' methods for computing the QR decomposition are P-complete, and hence presumably inherently sequential, under both real and floating point number models. We also prove that Gaussian Elimination (GE) with a weak form of pivoting, which only aims at making the resulting Algorithm nondegenerate (but possibly unstable) is likely to be inherently sequential as well. Finally, we prove that GE with partial pivoting is P-complete when restricted to Symmetric Positive Definite matrices, for which it is known that even plain GE does not fail. Altogether, the results of this paper give further formal support to the widespread belief that there is a tradeoff between parallelism and accuracy in numerical algorithms.

Bibliographic Notes

ICSI Technical Report TR-97-032

Abbreviated Authors

M. Leoncini, G. Manzini, and L. Margara

ICSI Publication Type

Technical Report