On the Parallel Complexity of Gaussian Elimination with Pivoting

摘要

Consider the Gaussian elimination algorithm with the well-known partial pivoting strategy for improving numerical stability (GEPP). Vavasis proved that the problem of determining the pivot sequence used by GEPP is log space-complete forP, and thus inherently sequential. AssumingP≠C, we prove here that either the latter problem cannot be solved in parallel timeO(N1/2−ε) or all the problems inPadmit polynomial speedup. HereNis the order of the input matrix andεis any positive constant. This strengthens the P-completeness result mentioned above. We conjecture that the result proved in this paper holds for the stronger boundO(N1−ε) as well, and provide supporting evidence for the conjecture. Note that this is equivalent to asserting the asymptotic optimality of the naive parallel algorithm for GEPP (moduloP≠NC).