GAUSSIAN ELIMINATION ON HYPERCUBES.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations

Abstract

We compare several implementations of the Gaussian elimination algorithm for solving dense linear systems on hypercube parallel processors. We distinguish between two classes of methods: methods that require to move the elimination row (or column) to all processors before the elimination proceeds, and methods that require only moving data to nearest neighbors. Algorithms of the second class, which we call pipelined algorithms, require only a ring or grid structure which is embedded into the hypercube. One of our main conclusions is that for Gaussian elimination the additional connectivity of the hypercube topology over that a two-dimensional grid of processors does not help much in improving efficiency. Another result of our analysis is that there is little reason for using row or column type algorithms instead of grid algorithms. One of the goals of the paper is also to show a simple model of complexity analysis at work, by comparing the estimated times that it provides with the actual execution times.

Original languageEnglish (US)
Title of host publicationUnknown Host Publication Title
EditorsMichel Cosnard, Yves Robert, Patrice Quinton, Maurice Tchuente
PublisherNorth-Holland
Pages5-17
Number of pages13
ISBN (Print)0444701044
StatePublished - Dec 1 1986

Fingerprint Dive into the research topics of 'GAUSSIAN ELIMINATION ON HYPERCUBES.'. Together they form a unique fingerprint.

Cite this