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).
53
380
394
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.
Leoncini, Mauro
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento 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/454045
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact