Rank annihilation on a ring of processors
type: Item
instance of: scholarly article
title: Rank annihilation on a ring of processors
zbMATH Open document ID: 0693.65022
DOI: 10.1016/0167-8191(90)90121-O
published in: Parallel Computing
publication date: 1990-01-01T00:00:00Z
review text: This paper presents a wavefront algorithm for computing the inverse \(B^{-1}\) of a matrix B which differs from an \(n\times n\) matrix A (whose inverse is known) in only a single row or column, by using the Sherman-Morrison formula. The solution is the result of two design steps: the first maps a 2-D systolic control ring instruction processor mesh into a 1-D array simulation while the second compacts the 1-D array by simulating sections of the ring as virtual arrays. It is proved that it requires 5n inner product (equivalent) steps using a ring of n processors with memory for \(2(n+1)\) values. For large values of n, by working with a ring of z processors, the partitioned version of the algorithm requires \(n(3k+2)\) inner product (equivalent) steps, where \(z=n/k\). An occam definition of the partitioned cell and array specification is given. It is shown that the design can be made fault tolerant. Some test results obtained by using a 5-transputer ring are also discussed. Besides their intrinsic value, the obtained results offer the possibility for developing pipelined versions of some more complex numerical methods requiring much computations.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65Y05
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 4135301
zbMATH Keywords: processor ring
zbMATH Keywords: rank annihilation
zbMATH Keywords: partitioning
zbMATH Keywords: arrays mapping
zbMATH Keywords: transputer
zbMATH Keywords: matrix inversion
zbMATH Keywords: wavefront algorithm
zbMATH Keywords: Sherman-Morrison formula
author: Graham M. Megson
MaRDI profile type: Publication
full work available at URL: 0167-8191(90)90121-o
OpenAlex ID: W1965077986
description: scientific article; zbMATH DE number 4135301