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 è be any positive constant. Assuming P ≠ NC, we prove that if GEPP were decidable in parallel time M1/2–è 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
1994-01-01
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 è be any positive constant. Assuming P ≠ NC, we prove that if GEPP were decidable in parallel time M1/2–è 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).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
