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.
Data di pubblicazione: | 1994 |
Titolo: | How much can we speedup Gaussian elimination with pivoting? |
Autore/i: | Leoncini, Mauro |
Autore/i UNIMORE: | |
Codice identificativo Scopus: | 2-s2.0-0011657810 |
Nome del convegno: | Parallel Algorithms and Architectures |
Luogo del convegno: | Cape May, New Jersey, United States |
Data del convegno: | 27 - 29 giugno 1994 |
Pagina iniziale: | 290 |
Pagina finale: | 297 |
Citazione: | 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. |
Tipologia | Relazione in Atti di Convegno |
File in questo prodotto:

I documenti presenti in Iris Unimore sono rilasciati con licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia, salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris