Rank annihilation on a ring of processors
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.
This page was built for publication: Rank annihilation on a ring of processors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908656)
