Optimal scheduling algorithms for parallel Gaussian elimination
type: Item
instance of: scholarly article
title: Optimal scheduling algorithms for parallel Gaussian elimination
zbMATH Open document ID: 0681.65014
DOI: 10.1016/0304-3975(89)90059-5
author: Denis Trytram
author: Yves Robert
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65Y05
zbMATH DE Number: 4115823
zbMATH Keywords: parallel algorithm
zbMATH Keywords: shared memory machine
zbMATH Keywords: 3-step scheduling algorithm
zbMATH Keywords: Gaussian elimination
zbMATH Keywords: asymptotic efficiency
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90059-5
OpenAlex ID: W3002895390
cites work: Q3747616
cites work: Q4728241
cites work: Q4734762
cites work: Implementing Linear Algebra Algorithms for Dense Matrices on a Vector Pipeline Machine
cites work: Q5185900
cites work: Q3674026
cites work: Q3318088
cites work: Solving Linear Algebraic Equations on an MIMD Computer
cites work: Q3729907
cites work: Communication complexity of the Gaussian elimination algorithm on multiprocessors
cites work: On Stable Parallel Linear System Solvers
description: scientific article; zbMATH DE number 4115823