Optimal algorithms for Gaussian elimination on an MIMD computer (Q912562)

A graph theoretic approach is used to derive asymptotically optimal algorithms for parallel LU decomposition with partial pivoting on an MIMD computer for a dense \(n\times n\) nonsingular matrix using \(p=\alpha n\) processors, \(\alpha\leq 1\). An algorithm is asymptotically optimal if its efficiency is maximum for \(n\to \infty\). The asymptotic efficiency \(e_{\alpha}=1/(1+\alpha^ 3)=0.959\) for \(\alpha \leq \alpha_ 0\simeq 0.347\) and \(e_{\alpha}=1/(3\alpha)\) for \(\alpha \geq \alpha_ 0\) is proved, where \(\alpha_ 0\) is the solution of the equation \(3\alpha - \alpha^ 3=1\). A high degree of parallelism can be achieved for \(\alpha \leq \alpha_ 0\). The derived lower bound improves the results by \textit{R. E. Lord}, \textit{J. S. Kowalik} and \textit{S. P. Kumar} [J. Assoc. Comput. Mach. 30, 103-117 (1983; Zbl 0502.65017)] for the minimum of processors (the smallest \(\alpha\)) required to achieve the parallel execution in time \(T_{opt}=n^ 2+0(n)\).