On the Parallel Complexity of Gaussian Elimination with Pivoting

TitleOn the Parallel Complexity of Gaussian Elimination with Pivoting
Publication TypeTechnical Report
Year of Publication1994
AuthorsLeoncini M
Other Numbers898
KeywordsGaussian Elimination with Partial Pivoting, NC class, P-complete problems, polynomial speedup, strict P-completeness

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 for P, and thus inherently sequential. Assuming P ? NC, we prove here that either the latter problem cannot be solved in parallel time O(N^{1/2-epsilon) or all the problems in P admit polynomial speedup. Here N is the order of the input matrix and epsilon 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 bound O(N^{1-epsilon}) as well, and provide supporting evidence to the conjecture. Note that this is equivalent to assert the asymptotic optimality of the naive parallel algorithm for GEPP (modulo P ? NC).

Bibliographic Notes

ICSI Technical Report TR-94-028

Abbreviated Authors

M. Leoncini

ICSI Publication Type

Technical Report