Data allocation strategies for the Gauss and Jordan algorithms on a ring of processors
type: Item
instance of: scholarly article
title: Data allocation strategies for the Gauss and Jordan algorithms on a ring of processors
zbMATH Open document ID: 0681.65015
DOI: 10.1016/0020-0190(89)90104-X
author: Bernard Tourancheau
author: Gilles Villard
author: Yves Robert
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: The problem is to determine the allocation function minimizing the total time complexity defined as the sum of the arithmetic time and the communication time for the parallel implementation of the Gauss and Jordan elimination methods on a ring of processors. It is supposed that no overlap occurs between computations and communications. The asymptotic optimality of the block repartition is proved for the Jordan elimination. Its efficiency is \(e_{\alpha}=1/[1+\alpha (1+\alpha)\rho],\) where \(\rho\) is the ratio of the elemental communication/computation costs for a problem of size n with \(p=\alpha n\) processors, \(0<\alpha \leq 1\). Various allocation functions are considered for the Gauss elimination, where data are wrapped among the processors by blocks of size r. The execution time for Gauss elimination is proved as a function of \(\alpha\) and \(\rho\). The value of r which is optimal and the efficiency for a block-r repartition are derived. The agreement of the theoretical results with the numerical experiments on a hypercube is pointed out.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65Y05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68N25
Mathematics Subject Classification ID: 65F30
zbMATH DE Number: 4115824
zbMATH Keywords: parallel architecture
zbMATH Keywords: allocation function
zbMATH Keywords: total time complexity
zbMATH Keywords: parallel implementation
zbMATH Keywords: ring of processors
zbMATH Keywords: Jordan elimination
zbMATH Keywords: Gauss elimination
zbMATH Keywords: numerical experiments
zbMATH Keywords: hypercube
MaRDI profile type: Publication
cites work: Parallel Gaussian elimination on an MIMD computer
cites work: Q3706408
cites work: Q3802494
cites work: On the Impact of Communication Complexity on the Design of Parallel Numerical Algorithms
cites work: Some Complexity Results for Matrix Computations on Parallel Processors
cites work: Complexity of dense-linear-system solution on a multiprocessor ring
cites work: Solving Linear Algebraic Equations on an MIMD Computer
cites work: The ijk forms of factorization methods. II: Parallel systems
cites work: Communication complexity of the Gaussian elimination algorithm on multiprocessors
cites work: Q4721511
full work available at URL: 0020-0190(89)90104-x
OpenAlex ID: W2070588089
description: scientific article; zbMATH DE number 4115824