Publication Details
Title: Parallel Complexity of Numerically Accurate Linear System Solvers
Author: M. Leoncini, G. Manzini, and L. Margara
Group: ICSI Technical Reports
Date: August 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-032.pdf
Overview:
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 (GE) with a weak form of pivoting, which only aims at making the resulting Algorithm nondegenerate (but possibly unstable) is likely to be inherently sequential as well. Finally, we prove that GE with partial pivoting is P-complete when restricted to Symmetric Positive Definite matrices, for which it is known that even plain GE 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.
Bibliographic Information:
ICSI Technical Report TR-97-032
Bibliographic Reference:
M. Leoncini, G. Manzini, and L. Margara. Parallel Complexity of Numerically Accurate Linear System Solvers. ICSI Technical Report TR-97-032, August 1997
Author: M. Leoncini, G. Manzini, and L. Margara
Group: ICSI Technical Reports
Date: August 1997
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1997/tr-97-032.pdf
Overview:
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 (GE) with a weak form of pivoting, which only aims at making the resulting Algorithm nondegenerate (but possibly unstable) is likely to be inherently sequential as well. Finally, we prove that GE with partial pivoting is P-complete when restricted to Symmetric Positive Definite matrices, for which it is known that even plain GE 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.
Bibliographic Information:
ICSI Technical Report TR-97-032
Bibliographic Reference:
M. Leoncini, G. Manzini, and L. Margara. Parallel Complexity of Numerically Accurate Linear System Solvers. ICSI Technical Report TR-97-032, August 1997