Consider the Gaussian elimination algorithm with the well-knownpartial pivoting strategy for improving numerical stability (GEPP).Vavasis proved that the problem of determining the pivot sequenceused by GEPP is log space-complete for P, and thus inherently sequential.Assuming P{NC, we prove here that either the latter problemcannot be solved in parallel time O(N^(1/2-eps)) or all the problems in Padmit polynomial speedup. Here N is the order of the input matrix and= is any positive constant. This strengthens the P-completeness resultmentioned above. We conjecture that the result proved in this paperholds for the stronger bound O(N^(1-eps)) as well, and provide supportingevidence for the conjecture. Note that this is equivalent to asserting theasymptotic optimality of the naive parallel algorithm for GEPP (moduloP different from NC).
On the Parallel Complexity of Gaussian Elimination with Pivoting / Leoncini, Mauro. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - STAMPA. - 53:(1996), pp. 380-394.
On the Parallel Complexity of Gaussian Elimination with Pivoting
LEONCINI, Mauro
1996
Abstract
Consider the Gaussian elimination algorithm with the well-knownpartial pivoting strategy for improving numerical stability (GEPP).Vavasis proved that the problem of determining the pivot sequenceused by GEPP is log space-complete for P, and thus inherently sequential.Assuming P{NC, we prove here that either the latter problemcannot be solved in parallel time O(N^(1/2-eps)) or all the problems in Padmit polynomial speedup. Here N is the order of the input matrix and= is any positive constant. This strengthens the P-completeness resultmentioned above. We conjecture that the result proved in this paperholds for the stronger bound O(N^(1-eps)) as well, and provide supportingevidence for the conjecture. Note that this is equivalent to asserting theasymptotic optimality of the naive parallel algorithm for GEPP (moduloP different from NC).Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris