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).
1994
Parallel Algorithms and Architectures
Cape May, New Jersey, United States
27 - 29 giugno 1994
290
297
Leoncini, Mauro
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).
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/465526
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact