Consider the problem of determining the pivot sequence used by the Gaussian Elimination algorithm with Partial Pivoting (GEPP). Let N stand for the order of the input matrix and let &egr; be any positive constant. Assuming P ≠ NC, we prove that if GEPP were decidable in parallel time M1/2–&egr; then all the problems in P would be characterized by polynomial speedup. This strengthens the P-completeness result that holds of GEPP. We conjecture that our result is valid even with the exponent 1 replaced for 1/2, and provide supporting arguments based on our result. This latter improvement would demonstrate the optimality of the naive parallel algorithm for GEPP (modulo P ≠ NC).
How much can we speedup Gaussian elimination with pivoting? / Leoncini, Mauro. - STAMPA. - (1994), pp. 290-297. (Intervento presentato al convegno Parallel Algorithms and Architectures tenutosi a Cape May, New Jersey, United States nel 27 - 29 giugno 1994).
How much can we speedup Gaussian elimination with pivoting?
LEONCINI, Mauro
1994
Abstract
Consider the problem of determining the pivot sequence used by the Gaussian Elimination algorithm with Partial Pivoting (GEPP). Let N stand for the order of the input matrix and let &egr; be any positive constant. Assuming P ≠ NC, we prove that if GEPP were decidable in parallel time M1/2–&egr; then all the problems in P would be characterized by polynomial speedup. This strengthens the P-completeness result that holds of GEPP. We conjecture that our result is valid even with the exponent 1 replaced for 1/2, and provide supporting arguments based on our result. This latter improvement would demonstrate the optimality of the naive parallel algorithm for GEPP (modulo P ≠ 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
