Parallel Complexity of Numerically Accurate Linear System Solvers

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.

ICSI Technical Report TR-97-032

Technical Report