Parallel Gaussian elimination on an MIMD computer (Q1096997)

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 \textit{J. J. Dongarra}, \textit{F. G. Gustavson} and \textit{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.