An optimal schedule for Gaussian elimination on an MIMD architecture (Q2570029)

The author gives a scheduling of the tasks for the Gaussian elimination procedure on an MIMD (multiple instruction, multiple data) parallel computer. It is shown that with \(n\) processors for a matrix of size \(n\), the overhead has an upper bound that is, except for some polylog factor, of the optimal order \(O(n^{3/2})\). This is a considerable improvement of the result by \textit{E. Bampis, J. C. Konig} and \textit{D. Trystram} [Parallel Comput. 17, No. 1, 55--61 (1991; Zbl 0725.65030)].