Optimal algorithms for Gaussian elimination on an MIMD computer

DOI10.1016/0167-8191(89)90052-5MaRDI QIDQ912562zbMATH OpenOpenAlexFDO

Authors Mounir Marrakchi, Yves Robert

Publication date 1989

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-8191(89)90052-5

zbMATH Keywords

asymptotically optimal algorithmscomplexity analysisGaussian eliminationMIMD computerparallel LU decompositionpartial pivotingtask graph

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05) Theory of operating systems (68N25) Analysis of algorithms and problem complexity (68Q25)

Review text

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)\).

Recommendations

• Parallel Gaussian elimination on an MIMD computer
• scientific article; zbMATH DE number 3984455
• An optimal algorithm for Gaussian elimination of band matrices on an MIMD computer
• scientific article; zbMATH DE number 4078622
• scientific article; zbMATH DE number 4084838

Cited in

(6)

• Parallel Gaussian elimination on an MIMD computer
• An optimal schedule for Gaussian elimination on an MIMD architecture
• scientific article; zbMATH DE number 3845037 (Why is no real title available?)
• scientific article; zbMATH DE number 3984455 (Why is no real title available?)
• scientific article; zbMATH DE number 4084838 (Why is no real title available?)
• An optimal algorithm for Gaussian elimination of band matrices on an MIMD computer

This page was built for publication: Optimal algorithms for Gaussian elimination on an MIMD computer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q912562)