Optimal scheduling algorithms for parallel Gaussian elimination (Q1823614)

The asymptotic efficiency of a parallel algorithm is defined as the limit of \(T_ 1/(pT_ p)\) for \(n\to \infty\), where n is the order of the matrix, p is the number of processors, and \(T_ 1\) and \(T_ p\) are the execution times for the sequential and parallel algorithms, respectively. For a shared memory machine with \(p=\alpha n\) processors \((\alpha <1)\), and with the assumption that synchronization and communication costs can be neglected, this paper describes a rather complicated, 3-step scheduling algorithm for Gaussian elimination with asymptotic efficiency \((1+\alpha^ 3)^{-1}\). It is also shown that this efficiency is optimal. The paper is mainly of theoretical interest, in particular due to the assumptions and the complicated second step of the algorithm.