On the Parallel Complexity of Gaussian Elimination with Pivoting
Title | On the Parallel Complexity of Gaussian Elimination with Pivoting |
Publication Type | Technical Report |
Year of Publication | 1994 |
Authors | Leoncini, M. |
Other Numbers | 898 |
Keywords | Gaussian Elimination with Partial Pivoting, NC class, P-complete problems, polynomial speedup, strict P-completeness |
Abstract | 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). |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1994/tr-94-028.pdf |
Bibliographic Notes | ICSI Technical Report TR-94-028 |
Abbreviated Authors | M. Leoncini |
ICSI Publication Type | Technical Report |