A new highly convergent Monte Carlo method for matrix computations1Supported by The Royal Society (UK), partially supported by the NATO Grant R406/02640 and by the Ministry of Science and Education of Bulgaria under Grants no. I 501 and no. MM 449.1

In this paper a second degree iterative Monte Carlo method for solving systems of linear algebraic equations and matrix inversion is presented. Comparisons are made with iterative Monte Carlo methods with degree one. It is shown that the mean value of the number of chains N, and the chain length T, required to reach given precision can be reduced. The following estimate on N is obtained: N=Nc/(cN+bN1/2c)2, where Nc is the number of chains in the usual degree one method. In addition it is shown that b>0 and that N<Nc/c2N. This result shows that for our method the number of realizations N can be at least c2N times less than the number of realizations Nc of the existing Monte Carlo method. For parallel implementation, i.e. regular arrays or MIMD distributed memory architectures, these results imply faster algorithms and the reduction of the size of the arrays. This leads also in applying such methods to the problems with smaller sizes, since until now Monte Carlo methods are applicable for large scale problems and when the component of the solution vector or element or row of the inverse matrix has to be found.