EFFICIENT PARALLEL MONTE-CARLO METHODS FOR MATRIX COMPUTATIONS

Three Monte Carlo methods for matrix inversion (MI) and finding a solu tion vector of a system of linear algebraic equations (SLAE) are consi dered: with absorption, without absorption with uniform transition fre quency function, and without absorption with almost optimal transition frequency function. Recently Alexandrov, Megson, and Dimov have shown that an n x n matrix can be inverted in 3n/2 + N + T steps on a regul ar array with O(n(2) NT) cells. Alexandrov and Megson have also shown that a solution vector of SLAE can be found in n + N + T steps on a re gular array with the same number of cells. A number of bounds on N and T have been established (N is the number of chains and T is the lengt h of the chain in the stochastic process; these are independent of n), which show that these designs are faster than existing designs for la rge values of n. In this paper we take another implementation approach ; we consider parallel Monte Carlo algorithms for MI and solving SLAE in MIMD environment, e.g. running on a cluster of workstations under P VM. The Monte Carlo method with almost optimal frequency function perf orms best of the three methods; it needs about six to ten times fewer chains for the same precision. (C) 1998 IMACS/Elsevier Science B.V.