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