SYSTOLIC MATRIX INVERSION USING A MONTE CARLO METHOD
Graham M. Megson, В. Н. Александров, Ivan Dimov · International Journal of Parallel Emergent and Distributed Systems · 1994
A systolic array for inverting an n × 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.