Gauss elimination algorithms for MIMD computers. (English) Zbl 0608.65017

Cosnard, M.; Marrakchi, M.; Robert, Y.; Trystram, D.

CONPAR 86, Algorithms and hardware for parallel processing, Proc. Conf., Aachen/Ger. 1986, Lect. Notes Comput. Sci. 237, 247-254 (1986).

[For the entire collection see Zbl 0597.00031.]
This paper uses a graph-theoretic approach to analyse the performances of several parallel variations of the Gaussian triangularization algorithm on an MIMD computer. J. Dongarra, F. Gustavson and A. Karp [SIAM Rev. 26, 91-112 (1984; Zbl 0539.65009)] have studied various parallel implementations of this method for a vector pipeline machine. We obtain complexity results permitting to select among these parallel algorithms.

MSC:

65F05	Direct numerical methods for linear systems and matrix inversion
68N25	Theory of operating systems

Keywords:

Gauss elimination; Gaussian triangularization algorithm; MIMD computer; parallel implementations; vector pipeline machine; complexity; parallel algorithms