Monte Carlo method and asynchronous iterations

Abstract

Asynchronous methods as well as Monte Carlo methods play an important role in using multiprocessor (multicore) computations and investigation of the connections between them and, especially, expansion the field of the irapplicability are important problems. System of theform x = Ax+f is considered, where x is unknown column-vector of length n, F is a column-vector of the right-hand sides of length n, A is n × n-matrix of the system. Case when the first eigenvalue of |A|less than 1 is well studied and in that case there are close connections between asynchronous iterations and Monte Carlo method. If the first eigenvalue of |A|is greater than 1, whereas the first eigenvalue of A less than 1, then similar methods appear to be inapplicable. New modifications of Monte Carlo method and asynchronous method with partial synchronization are proposed. Estimates of the errors and convergence conditions for proposed methods are obtained depending on the ratio are obtained. Numerical experiments areperformed.

Keywords:

Monte Carlo methods, asynchronous methods, asynchronous iterations, parallel algorithms, statistical modeling