Parallel complexity of numerically accurate linear system solvers

Mauro Leoncini, Giovanni Manzini, Luciano Margara

Risultato della ricerca: Contributo su rivistaArticolo in rivistapeer review

Abstract

We prove a number of negative results about practical (i.e., work efficient and numerically accurate) algorithms for computing the main matrix factorizations. In particular, we prove that the popular Householder and Givens methods for computing the QR decomposition are P-complete, and hence presumably inherently sequential, under both real and floating point number models. We also prove that Gaussian elimination (GB) with a weak form of pivoting, which aims only at making the resulting algorithm nondegenerate, is likely to be inherently sequential as well. Finally, we prove that GE with partial pivoting is P-complete over GF(2) or when restricted to symmetric positive definite matrices, for which it is known that even standard GE (no pivoting) does not fail. Altogether, the results of this paper give further formal support to the widespread belief that there is a tradeoff between parallelism and accuracy in numerical algorithms.

Lingua originaleInglese
pagine (da-a)2000-2058
Numero di pagine59
RivistaSIAM Journal on Computing
Volume28
Numero di pubblicazione6
DOI
Stato di pubblicazionePubblicato - 1999
Pubblicato esternamente

Fingerprint

Entra nei temi di ricerca di 'Parallel complexity of numerically accurate linear system solvers'. Insieme formano una fingerprint unica.

Cita questo