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 factori zations. In particular, we prove that the popular Householder and Givens me thods for computing the QR decomposition are P-complete, and hence presumab ly inherently sequential, under both real and floating point number models. We also prove that Gaussian elimination (GE) with a weak form of pivoting, which aims only at making the resulting algorithm nondegenerate, is likely to be inherently sequential as well. Finally, we prove that GE with partia l pivoting is P-complete over GF(2) or when restricted to symmetric positiv e definite matrices, for which it is known that even standard GE (no pivoti ng) does not fail. Altogether, the results of this paper give further forma l support to the widespread belief that there is a tradeoff between paralle lism and accuracy in numerical algorithms.