Reducing computational cost of the multilevel Monte Carlo method by construction of suitable pathwise integrators

Abstract

The multilevel Monte Carlo (MLMC) method has been recently proposed as a variance reduction technique for the efficient estimation of expected values of the quantities of interest associated with solutions of stochastic and random differential equations.

By combining the ideas of multigrid discretization and Monte Carlo sampling, it allows to achieve the optimal asymptotical complexity of the estimator for the very large class of problems.

The actual cost of the estimator, however, is more problem and solver dependent as the method requires one to solve a large number of decoupled deterministic problems.

The efficiency of the estimator is hence strongly influenced by the complexity of the corresponding pathwise integrators.

It is the task of this dissertation to study several problems for which the significant reduction in the computational complexity of the MLMC estimator can be achieved by the appropriate problem and level dependent choice of deterministic solvers.

Three particular problems are considered: integration of stiff SDEs, estimation of initial guesses for iterative linear solvers and boundary values problems in randomly perturbed domains.

The brief description of each problem is given below.

In Chapter II, we consider acceleration of the MLMC method in application to stochastic differential equations (SDEs).

SDEs are often used in modeling of time-dependent phenomena at the mesoscopic level.

Physical systems at this level are characterized by the presence of the vast range of temporal scales which makes them intrinsically stiff.

In stochastic setting, stiffness is a serious issue in numerical treatment of differential systems due to non-trivial interaction between noise and multiscale dynamics.

%The goal of this project was to construct efficient implicit integrators capable to generate stable solutions without destroying geometry of the true stochastic dynamics.

To resolve this issue, we propose the family of split-step implicit integrators which are capable to generate stable solutions without destroying geometry of the true stochastic dynamics.

In the context of the MLMC method, the proposed integrators allow to exploit all the levels of the multilevel discretization without the need to explicitly resolve the fastest scale of the dynamics.

The efficiency of the proposed technique is illustrated by applying it to stiff stochastic chemical systems and both qualitative and quantitative results are presented.

Chapter III is devoted to the acceleration of the MLMC method in application to partial differential equations (PDEs) with random input data.

As was mentioned above, MLMC requires solving a large number of decoupled deterministic problems corresponding to different realizations of input data.

For stationary partial differential equations, these solutions are often constructed by means of iterative process and the choice of initial guess can have a drastic influence on its convergence.

It will be shown that the estimation of initial guesses to iterative solvers can be efficiently performed by recycling previously calculated data.

For this purpose, we use the kernel based approximation technique and perform the asymptotic cost analysis of the accelerated method to illustrate its superiority.

Finally, partial differential equations in random domains are discussed in Chapter IV.

Problems with topological uncertainties appear in many fields ranging from nano-device engineering and analysis of micro electromechanical systems to design of bridges.

In many of such problems, only part of the domain is subjected to random perturbations and conventional schemes relying on discretization of the whole domain become inefficient.

We study linear PDEs in domains with boundaries comprised of both deterministic and random parts and apply the method of modified potentials with kernels given by the Green's functions defined on the deterministic part of the domain.

This approach allows to reduce the size of the original differential problem by reformulating it as a boundary integral equation posed on the random part of the boundary only.

The MLMC method is then applied to this modified integral equation leading to significant computational savings.

We provide the qualitative analysis of the proposed technique and support it with numerical results.