More Parallelism into the Monte Carlo Solution of Partial Differential Equations

Abstract:

The Monte Carlo Method has been studied and used to solve elliptic and parabolic partial differential equations. It has several numerical and computational advantages over other methods. The main computational advantage is the great amount of inherent parallelism it manifests. However, an often costly part of the method has remained sequential. It is the random-walk computation (RWC). In this report we parallelize (RWC) using fan-in and fan-out methods. The parallel algorithm takes O(log n) time while the sequential one takes O(n) where n is the average random-walk length.