A recursive doubling algorithm for solution of tridiagonal systems on hypercube multiprocessors
type: Item
instance of: scholarly article
title: A recursive doubling algorithm for solution of tridiagonal systems on hypercube multiprocessors
zbMATH Open document ID: 0679.65018
DOI: 10.1016/0377-0427(89)90362-2
author: Ömer Eğecioğlu
author: Çetin Kaya Koç
author: Alan J. Laub
published in: Journal of Computational and Applied Mathematics
publication date: 1989-01-01T00:00:00Z
review text: The authors give a limited processor version of the recursive doubling algorithm for the solution of tridiagonal linear systems using parallel arithmetic steps on a parallel computer. They make use of fast parallel prefix algorithms. The algorithm achieves linear speedup and constant efficiency over its sequential implementation. Computational results are given based on an Intel iPSC/d5 hypercube multiprocessor. The authors are in the process of extending the proposed algorithm to general recurrence relations, block tridiagonal and banded linear systems.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65Y05
zbMATH DE Number: 4113847
zbMATH Keywords: block tridiagonal linear systems
zbMATH Keywords: recursive doubling algorithm
zbMATH Keywords: parallel computer
zbMATH Keywords: parallel prefix algorithms
zbMATH Keywords: linear speedup
zbMATH Keywords: efficiency
zbMATH Keywords: hypercube multiprocessor
zbMATH Keywords: recurrence relations
zbMATH Keywords: banded linear systems
describes a project that uses: LINPACK
MaRDI profile type: Publication
full work available at URL: 0377-0427(89)90362-2
OpenAlex ID: W2170745229
cites work: Q5540873
cites work: Q3932291
cites work: A stability classification method and its application to pipelined solution of linear recurrences
cites work: A Survey of Parallel Algorithms in Numerical Linear Algebra
cites work: Solving Tridiagonal Systems on Ensemble Architectures
cites work: A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations
cites work: Parallel Prefix Computation
cites work: Hypercube Algorithms and Implementations
cites work: Computational Complexity and Numerical Stability
cites work: Solution of Partial Differential Equations on Vector and Parallel Computers
cites work: Q3936208
cites work: Stability aspects in using parallel algorithms
cites work: An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations
cites work: Parallel Tridiagonal Equation Solvers
cites work: Perturbation Theory for Evaluation Algorithms of Arithmetic Expressions
description: scientific article; zbMATH DE number 4113847