G.M. Megson
V. N. Aleksandrov
I.T. Dimov
University of Newcastle upon Tyne. 1994
A systolic array for inverting an n x n matrix using a Monte-Carlo method is proposed. The basic array computes a single row of the inverse in 3n + N + T steps (including input and output time) and O (nNT ) cells where N is the number of chains and T is the length of each chain in the stochastic process. A full inverse is computed in the same time but requires O (n2NT ) cells. Further improvements reduce the time to 3n/2 + N + T using the same number of cells. A number of bounds on N and T are established which show that our design is faster than existing designs for reasonably large values of n. Indeed the final arrays require less than n4 cells and have a computing time bounded above by 4n.