Optimal scheduling algorithms for parallel Gaussian elimination (Q1823614): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Yves Robert / rank | |||
Property / author | |||
Property / author: Yves Robert / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(89)90059-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3002895390 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3747616 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4728241 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4734762 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Implementing Linear Algebra Algorithms for Dense Matrices on a Vector Pipeline Machine / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5185900 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3674026 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3318088 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Solving Linear Algebraic Equations on an MIMD Computer / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3729907 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Communication complexity of the Gaussian elimination algorithm on multiprocessors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Stable Parallel Linear System Solvers / rank | |||
Normal rank |
Latest revision as of 10:44, 20 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimal scheduling algorithms for parallel Gaussian elimination |
scientific article |
Statements
Optimal scheduling algorithms for parallel Gaussian elimination (English)
0 references
1989
0 references
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.
0 references
parallel algorithm
0 references
shared memory machine
0 references
3-step scheduling algorithm
0 references
Gaussian elimination
0 references
asymptotic efficiency
0 references