zbMATH — the first resource for mathematics

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.

65F05 Direct numerical methods for linear systems and matrix inversion
65Y05 Parallel numerical computation
68Q25 Analysis of algorithms and problem complexity
Zbl 0539.65009
Full Text: DOI