We study the complexity of some computational problems in case certain stability guarantees are required. After providing suitable settings for this kind of investigations, we are able to give theoretical support to longstanding viewpoints in numerical analysis. More precisely, we focus on a set of significant examples and prove that: (1) the fastest known polynomial evaluation algorithms are not stable, (2) LUP decomposition cannot be computed stably in polylogarithmic parallel time, and (3) reductions among computational problems do not in general constitute a practical tool for solving numerical problems.

On Speed versus Accuracy: Some Case Studies / Leoncini, Mauro. - In: JOURNAL OF COMPLEXITY. - ISSN 0885-064X. - STAMPA. - 12:(1996), pp. 239-253.

On Speed versus Accuracy: Some Case Studies

LEONCINI, Mauro
1996

Abstract

We study the complexity of some computational problems in case certain stability guarantees are required. After providing suitable settings for this kind of investigations, we are able to give theoretical support to longstanding viewpoints in numerical analysis. More precisely, we focus on a set of significant examples and prove that: (1) the fastest known polynomial evaluation algorithms are not stable, (2) LUP decomposition cannot be computed stably in polylogarithmic parallel time, and (3) reductions among computational problems do not in general constitute a practical tool for solving numerical problems.
12
239
253
On Speed versus Accuracy: Some Case Studies / Leoncini, Mauro. - In: JOURNAL OF COMPLEXITY. - ISSN 0885-064X. - STAMPA. - 12:(1996), pp. 239-253.
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/454047
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact