## 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

Zbl 0539.65009
Full Text: