Rank annihilation on a ring of processors (Q908656)

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.