Parallel Triangular System Solving on a Mesh Network of Transputers
Authors:
- Rob H. BisselingRBRob H. Bisseling
- Johannes G. G. van de VorstJVJohannes G. G. van de Vorst
- 1 July 1991
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific and Statistical Computing
- Vol. 12 (4) , 787-799
Abstract
A parallel algorithm is presented for triangular system solving on a distributed-memory MIMD computer with a square mesh topology. The algorithm is based on the square grid (scattered) distribution of matrix elements across the processors. The theoretical time complexity is $n^2/ p + O(n)$, for p processors and an $n \times n$ matrix. Experimental timings of an implementation in occam 2 on a square mesh of $p = 36$ transputers confirm the theoretical time model. The scaled speedup achieved for $n = 1200$ is 24 on a 36 transputer mesh. This corresponds to a computing rate of 11.7 Mflop/s.
Keywords
This publication has 15 references indexed in Scilit:
- Benchmarking the iPSC/2 hypercube multiprocessorConcurrency: Practice and Experience, 1989
- A New Method for Solving Triangular Systems on Distributed-Memory Message-Passing MultiprocessorsSIAM Journal on Scientific and Statistical Computing, 1989
- Parallel LU decomposition on a transputer network1989
- The formal construction of a parallel triangular system solverLecture Notes in Computer Science, 1989
- Development of Parallel Methods for a $1024$-Processor HypercubeSIAM Journal on Scientific and Statistical Computing, 1988
- Modified Cyclic Algorithms for Solving Triangular Systems on Distributed-Memory MultiprocessorsSIAM Journal on Scientific and Statistical Computing, 1988
- Parallel Solution of Triangular Systems on Distributed-Memory MultiprocessorsSIAM Journal on Scientific and Statistical Computing, 1988
- A Parallel Triangular Solver for a Distributed-Memory MultiprocessorSIAM Journal on Scientific and Statistical Computing, 1988
- Communication efficient basic linear algebra computations on hypercube architecturesJournal of Parallel and Distributed Computing, 1987
- The Science of Programming1981