Performance bounds for column-block partitioning of parallel Gaussian elimination and Gauss-Jordan methods
type: Item
instance of: scholarly article
title: Performance bounds for column-block partitioning of parallel Gaussian elimination and Gauss-Jordan methods
zbMATH Open document ID: 0814.65028
DOI: 10.1016/0168-9274(94)00051-4
author: Apostolos Gerasoulis
author: Tao Yang
published in: Applied Numerical Mathematics
publication date: 1995-06-18T00:00:00Z
review text: This paper gives asymptotic lower bounds for the performance of Gaussian elimination and the Gauss-Jordan algorithm on scalable distributed-memory parallel architectures. Asymptotic refers to the large size of the linear system being solved. Such bounds are given when the matrix is partitioned in square blocks or when it is column-partitioned. The bounds for the optimal schedule time are expressed in terms of the time needed to perform the actual flops, the start up time for processor communication, the transmission speed, the number of processors and of course, the size of the problem. Numerical experiments are discussed, which show that the bounds are close to the actual execution time on the nCUBE-2 machine.
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65Y05
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 721009
zbMATH Keywords: parallel numerical computing
zbMATH Keywords: block partitioning
zbMATH Keywords: task scheduling
zbMATH Keywords: numerical experiments
zbMATH Keywords: asymptotic lower bounds
zbMATH Keywords: performance
zbMATH Keywords: Gaussian elimination
zbMATH Keywords: Gauss-Jordan algorithm
zbMATH Keywords: distributed-memory parallel architectures
MaRDI profile type: Publication
full work available at URL: 0168-9274(94)00051-4
OpenAlex ID: W2032217381
cites work: On Graham's bound for cyclic scheduling
cites work: Column LU Factorization with Pivoting on a Message-Passing Multiprocessor
cites work: Q3134821
cites work: Solving Linear Algebraic Equations on an MIMD Computer
cites work: Towards an Architecture-Independent Analysis of Parallel Algorithms
cites work: Complexity of dense-linear-system solution on a multiprocessor ring
cites work: Data allocation strategies for the Gauss and Jordan algorithms on a ring of processors
cites work: Q3994933
cites work: Q4721511
description: scientific article; zbMATH DE number 721009