×

Parallel Gaussian elimination on an MIMD computer. (English) Zbl 0634.65017

This paper introduces a graph-theoretic approach to analyse the performances of several parallel Gaussian-like triangularization algorithms on an MIMD computer. We show that the SAXPY, GAXPY and DOT algorithms of J. J. Dongarra, F. G. Gustavson and A. Karp [SIAM Rev. 26, 91-112 (1984; Zbl 0539.65009)], as well as parallel versions of the \(LDM^ t\), \(LDL^ t\), Doolittle and Cholesky algorithms, can be classified into four task graph models. We derive new complexity results and compare the asymptotic performances of these parallel versions.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65Y05 Parallel numerical computation
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0539.65009
PDF BibTeX XML Cite
Full Text: DOI