COMPUTATIONAL IMPROVEMENTS FOR STOCHASTIC SIMULATION WITH MULTILEVEL MONTE CARLO

Abstract

In this work we implement various techniques to improve the multilevel Monte Carlo (MLMC) method as it is applied to a variety of stochastic models. In each case we were able to show a quantifiable computational benefit.

First we explore the use of a parallel antithetic MLMC algorithm to simulate systems of stochastic differential equations (SDEs) with correlated noise. Since Le ́vy area approxima- tion is unnecessary with antithetic MLMC, it is a natural choice for the solution of systems with non-diagonal, non-commutative noise. The Milstein method used with antithetic MLMC provides a computation complexity of O(ε^−2) root-mean-square error. Furthermore, MLMC uses independent sampling, which is naturally suited for parallel algorithms. We display the advantages of this approach with a case study in stochastic pricing models.

Secondly, we analyze the effects of stiffness on the convergence rate to the solution of a system of SDEs. Similarly to their deterministic counterparts, stochastic differential solvers can be unstable when used with a stiff system. When unstable step sizes are taken on the lower levels of MLMC, convergence is not guaranteed. We examine two approaches to remedy this problem: 1) the use of a semi-implicit method with a larger step-size stability region and 2) simply using a more fine discretization as the initial level for the MLMC simulator. We apply this approach to a case study in biochemical reaction networks.

Lastly, we improve a recently developed MLMC algorithm, which uses an iterative solver for the solution a partial differential equation (PDE) with random input. The innovation of the original algorithm is that each sample utilizes data gathered from all previously computed samples to create a better initial guess for the iterative solver. The drawback of this method is that the computation of a sample is no longer independent in a computational sense. We use a K-dimensional tree to sort the random input initially so that groups of locally distributed samples may be computed in batches at each parallel computing node.