Issues in the Software Implementation of Stochastic Numerical Runge–Kutta

Abstract

This paper discusses the application of stochastic Runge-Kutta-like numerical methods with weak and strong convergences for systems of stochastic differential equations in Itô form. At the beginning a brief overview of available publications about stochastic numerical methods and information from the theory of stochastic differential equations are given. Then the difficulties that arise when trying to implement stochastic numerical methods and motivate to use source code generation are described. We discuss some implementation details, such as program languages (Python, Julia) and libraries (Jinja2, Numpy). Also the link to the repository with source code is provided in the article.

1 Introduction

The article [16] describes the Python [30] implementation of stochastic numerical Runge-Kutta type methods. This implementations heavily relies on NumPy and SciPy [18] libraries. We chose Pyhon language because of it’s simplicity and development speed. NumPy’s capability to work with multidimensional arrays as tensors (functions and ) was also very helpful. However, the performance was low, and not so much because of Python slowness, as because we used the large number of nested loops (up to seven). In this paper, we consider an alternative approach of stochastic numerical methods implementation, based on automatic code generation.

This article is divided into three sections. The first section provides the overview of the main sources and presents information from the theory of stochastic differential equations (SDE) and methods for their numerical solution. The second section presents stochastic numerical schemes for scalar SDE with strong convergence and for SDE systems with strong and weak convergence. In addition to the general schemes, several coefficient tables are provided. This allows to implement a specific numerical method. Finally, the third section explains the use of code generation for stochastic numerical methods and describes some details of the generator we have implemented (we use Jinja2 [1] template engine).

2 Background Overview

In this section, we give a brief overview of the available publications on stochastic Runge-Kutta methods. We study multistage numerical schemes without partial derivatives from the drift vector $\mathbf {f}(t,\mathbf {X})$ and the diffusion matrix $\mathbf {G}(t,\mathbf {X})$, so we don’t consider Milstein methods [25,26,27]).

First, who used a stochastic Brownian process for mathematical modeling was a French mathematician, a student of Henri Poincare—Bachelier (1870–1946) in 1900 in the work [3].

The book by Kloeden and Platen [19] is classical work on numerical methods for SDE. The book provides a brief introduction to the theory of stochastic Ito and Stratonovich differential equations and their applications. The last two thirds of the book are devoted to the presentation of numerical methods in the sense of strict and weak approximations, including a number of Runge-Kutta methods.

The dissertation by Rößler [32] is a consistent report of stochastic numerical Runge-Kutta-like methods. The author considers the approximation of Ito and Stratonovich SDE systems in a weak sense for the scalar and multidimensional Wiener process. After a brief review of the previous works, the author develops the stochastic equivalent of labelled trees theory (labelled trees are used to derive the order conditions in the case of deterministic Runge-Kutta methods, see, for example, [13, 17]).

Rossler considers weakly convergent stochastic Runge-Kutta-like methods for Ito and Stratonovich SDE systems for both the scalar and the multidimensional Wiener process. In the third and the fifth part of the dissertation the specific implementation of the explicit stochastic numerical methods for weak convergence was described.

Further results of Rosler studies were described in articles [14, 15] in collaboration with Debrabant. In the preprint [15] authors continued classification of stochastic methods, Runge-Kutta method with a weak convergence. Several concrete realizations and results of numerical experiments were obtained. In the another preprint [31], they gave tables for fourth stage and strong order convergence methods $p=3.0$.

Euler–Maruyama method described by Maruyama in the paper [23] may be considered as the first stochastic Runge-Kutta-like method. The first systematic study of stochastic numerical Runge–Kutta-like methods of strong order of convergence $p=1.0$ is given by Rümelin [33] and Platen in his thesis [29].

Great contribution was made by Burrage and Burrage in a series of articles [7,8,9,10, 12]. In these papers, they not only studied methods of strong order $p=1.5$, but also extended the theory of labeled trees to the stochastic case.

The article of Soheili and Namjoo [34] presented the three methods with strong convergence $p=1.0$ and the numerical comparison with the method from the book [19].

Some of the first methods with weak convergence are given in the book [19]. Further development they received in article by Komori and Mitsui [20] and in [22]. In the article [35] two three-stage methods, the weak convergence of the $p=2.0$, as well as numerical experiments were introduced.

In view of the extreme complexity of further improving the order of accuracy of stochastic numerical schemes, the modern studies are devoted to obtaining numerical schemes for special SDE cases. It is possible to point out some of such studies about stochastic symplectic Runge–Kutta-like methods [11, 21, 37] and stochastic analogues of the Rosenbrock method [2].

3 Stochastic Wiener Process and Software Generation of Its Trajectories

The stochastic process W(t), $t \geqslant 0$ is called scalar Wiener process if the following conditions are true [19, 28]:

• $\mathrm {P}\{W(0)=0\} = 1$, or in other words, $W (0) = 0$ is almost certain;

• W(t) is process with independent increments, i.e. $\{\varDelta W_{i}\}^{N-1}_{0}$ are independent random variables: $\varDelta W_{I} = W(t_{I+1}) - W (t_{I})$ and $0 \leqslant t_{0}< t_{1}< t_{2}< \ldots < t_{N} \leqslant T$;

• $\varDelta W_{i} = W (t_{I+1}) - W (t_{I}) \sim \mathcal {N} (0, t_{I + 1}-t_{I})$ where $0\leqslant t_{I+1}< t_{I} < t$, $I=0,1,\ldots , N-1.$

The symbol $\varDelta W_{i} \sim \mathcal {N}(0,\varDelta t_{i})$ denotes that $\varDelta W_{i}$ is normally distributed random variable with expected value $\mathbb {E}[\varDelta W_{i}] = \mu = 0$ and variance $\mathbb {D}[\varDelta W_{i}] = \sigma ^{2} = \varDelta t_{i}$.

The Wiener process is a model of Brownian motion (random walk). If we consider the process W(t) in time points $0 = t_{0}< t_{1}< t_{2}< \ldots< t_{N-1} < t_{N}$ when it experiences random additive changes, then directly from the definition of Wiener process follows:

$$ W(t_{1}) = W(t_{0}) + \varDelta W_0, W(t_{2}) = W(t_{1}) + \varDelta W_1, \ldots , W(t_{N}) = W(t_{N-1}) + \varDelta W_{N-1}, $$

where $\varDelta W_{i} \sim \mathcal {N}(0,\varDelta t_{i})$, $\forall i = 0,\ldots ,N-1$.

The multidimensional Wiener process $\mathbf {W} (t):\varOmega \times [t_{0},T]\rightarrow \mathbb {R}^{m}$ is defined as a random process composed of jointly independent one-dimensional Wiener processes $W^{1} (t),\ldots ,W^{m} (t)$. Increments of $\varDelta W^{\alpha }_{I},\;\forall \alpha = 1,\ldots ,m$ are jointly independent normally distributed random variables. On the other hand, the vector $\varDelta W^{\alpha }_{I}$ can be represented as a multidimensional normally distributed random variable with the expectation vector $\mu = \mathbf {0}$ and the diagonal covariance matrix.

In the case of a multidimensional stochastic process one has to generate m sequences of n normally distributed random variables should be generated.

3.1 Program Generation of Wiener Process

To simulate a one-dimensional Wiener process, it is necessary to generate N normally distributed random numbers $\varepsilon _{1}, \ldots , \varepsilon _{N}$ and to construct their cumulative sums. The result will be the simulated sample path of the Wiener process W(t) or—using a different terminology—concrete implementation of the Wiener process.

In the case of a multidimensional random process, n sequences of m normally distributed random variables should be generated (that is, n arrays, each of m elements).

We implemented Wiener process generator in Python [30] and Julia [5]. To generate an array of numbers distributed according to the standard normal distribution in the case of Python, we used the function random.normal from the NumPy [18] library and, in the case of Julia, the built-in randn function. Both functions give qualitative pseudorandom sequences, since their work uses generators of uniformly distributed pseudorandom numbers based on an algorithm called Mersenne’s vortex [24] (Mersenne Twister), and generators of pseudorandom normally distributed numbers use the Box–Mueller transformation [4, 6].

To generate the Wiener process in Python one should use the WienerProcess class. The following code gives an example of this class usage.

The class constructor does not have any required arguments. By default, a process is generated on a time interval $[0,\;1]$, which is divided into 1000 parts (N=1000). Thus, by default, a path consisting of 1001 points with step dt equal to 0.001.

In the case of Julia, the Wiener process generator is implemented as the composite data type struct

With following contractors

3.2 Calculation and Approximation of Multiple Ito Integrals of Special Form

Here we will not go into the general theory of multiple stochastic Ito integrals, a reader can refer to the book [19] for additional information. Here we consider multiple special integrals, which are included in the stochastic numerical schemes.

In General, for the construction of numerical schemes with order of convergence greater than $p=\frac{1}{2}$, it is necessary to calculate single, double and triple Ito integrals of the following form:

$$ I^{\alpha }(t_{n}, t_{n+1}) = I^{\alpha }(h_{n}) = \int \limits _{t_{n}}^{t_{n+1}} \mathrm {d}W^{\alpha }(\tau ), $$

$$ I^{\alpha \beta }(t_{n}, t_{n+1}) = I^{\alpha \beta }(h_{n}) = \int \limits _{t_{n}}^{t_{n+1}}\int \limits _{t_{n}}^{\tau _{1}}\mathrm {d}W^{\alpha }(\tau _{2})\mathrm {d}W^{\beta }(\tau _{1}), $$

$$ I^{\alpha \beta \gamma }(t_{n}, t_{n+1}) = I^{\alpha \beta \gamma }(h_{n}) = \int \limits _{t_{n}}^{t_{n+1}}\int \limits _{t_{n}}^{\tau _{1}}\int \limits _{t_{n}}^{\tau _{2}}\mathrm {d}W^{\alpha }(\tau _{3})\mathrm {d}W^{\beta }(\tau _{2})\mathrm {d}W^{\gamma }(\tau _{1}), $$

where $\alpha ,\beta ,\gamma =0\ldots , m$ and $W^{\alpha },\alpha =1,\ldots , m$ are components of multidimensional Wiener process. In the case of $\alpha ,\beta ,\gamma = 0$, the increment of $\mathrm {d} W^{0}(\tau )$ is assumed to be $\mathrm {d} \tau$.

The problem is to get analytical formulas for these integrals with $\varDelta W^{I}_{n} = W^{I}(t_{n+1}) - W^{I}(t_{n})$ in them. Despite its apparent simplicity, this is not achievable for all possible combinations of indices. Let us consider in the beginning those cases when it is possible to obtain an analytical expression, and then turn to those cases when it is necessary to use an approximating formulas.

In the case of a single integral, the problem is trivial and the analytic expression can be obtained for any index $\alpha$:

$$ I^{0}(h_{n}) = \varDelta t_{n} = h_{n},\;\; I^{\alpha }(h_{n}) = \varDelta W^{\alpha }_{n},\;\alpha =1,\ldots ,m. $$

In the case of a double integral $I^{\alpha \beta } (h_{n})$, the exact formula takes place only at $\alpha =\beta$:

$$ I^{00}(h_{n}) = \dfrac{1}{2}\varDelta t_{n} = \dfrac{1}{2}h^{2}_{n},\;\; I^{\alpha \alpha }(h_{n}) = \dfrac{1}{2}\left( (\varDelta W^{\alpha }_{n})^2 - \varDelta t_{n} \right) ,\;\alpha =1,\ldots ,m, $$

in other cases, when $\alpha \ne \beta$ Express $I^{\alpha \beta } (h_{n})$ by increments of $\varDelta W^{\alpha }_{n}$ and $\varDelta t_{n}$ in the final form is not possible, so we can only use numerical approximation.

For the mixed case $I^{0\alpha }$ and $I^{\alpha 0}$ in [32], simple formulas of the following form are given:

$$ I^{0\alpha }(h_{n}) = \dfrac{1}{2}h_{n}\left( I^{\alpha }(h_{n}) - \frac{1}{\sqrt{3}}\zeta ^{\alpha }(h_{n})\right) , $$

$$ I^{\alpha 0}(h_{n}) = \dfrac{1}{2}h_{n}\left( I^{\alpha }(h_{n}) + \frac{1}{\sqrt{3}}\zeta ^{\alpha }(h_{n})\right) , $$

where $\zeta ^{\alpha }_{n}\sim \mathcal {N}(0,h_{n})$ are multidimensional normal distributed random variables.

For the General case $\alpha ,\beta = 1,\ldots , m$, the book [19] provides the following formulas for approximating the double Ito integral $I^{\alpha \beta }$:

$$\begin{aligned} \begin{array}{c} I^{\alpha \beta }(h_{n}) = \dfrac{\varDelta W^{\alpha }_{n} \varDelta W^{\beta }_{n} - h_{n}\delta ^{\alpha \beta }}{2} + A^{\alpha \beta }(h_{n}),\\ A^{\alpha \beta }(h_{n}) = \dfrac{h}{2\pi }\sum \limits ^{\infty }_{k=1}\dfrac{1}{k}\left[ V^{\alpha }_{k}\left( U^{\beta }_{k} + \sqrt{\frac{2}{h_{n}}} \varDelta W^{\beta }_{n}\right) - V^{\beta }_{k}\left( U^{\alpha }_{k} + \sqrt{\frac{2}{h_{n}}}\varDelta W^{\alpha }_{n}\right) \right] , \end{array} \end{aligned}$$

where $V^{\alpha }_{k} \sim \mathcal {N}(0,1)$, $U^{\alpha }_{k} \sim \mathcal {N}(0,1)$, $\alpha =1,\ldots ,m;\; k=1,\ldots ,\infty$; $n=1,\ldots ,N$ is numerical schema number. From the formulas it is seen that in the case $\alpha =\beta$, we get the final expression for the $I^{\alpha \beta }$, which we mentioned above. In the case of $\alpha \ne \beta$, one has to sum the infinite series $a^{\alpha \beta }$. This algorithm gives an approximation error of order $O(h^2/n)$, where n is number of left terms of an infinite series $a^{ij}$.

In the article [36] a matrix form of approximating formulas is introduced. Let $\mathbf {1}_{m\times m}$, $\mathbf {0}_{m\times m}$ be the unit and zero matrices $m\times m$, then

$$\begin{aligned} \begin{array}{c} \mathbf {I}(h_{n}) = \dfrac{\varDelta \mathbf {W}_{n} \varDelta \mathbf {W}^{T}_{n} - h_{n}\mathbf {1}_{m\times m}}{2} + \mathbf {A}(h_{n}),\\ \mathbf {A}(h_{n}) = \dfrac{h}{2\pi }\sum \limits ^{\infty }_{k=1}\dfrac{1}{k}\left( \mathbf {V}_{k}(\mathbf {U}_{k} + \sqrt{2/h_{n}} \varDelta \mathbf {W}_{n})^{T} - (\mathbf {U}_{k} + \sqrt{2/h_{n}}\varDelta \mathbf {W}_{n})\mathbf {V}^{T}_{k}\right) , \end{array} \end{aligned}$$

where $\varDelta \mathbf {W}_{n}, \mathbf {V}_{k}, \mathbf {U}_{k}$ are independent normally distributed multidimensional random variables:

$$\begin{aligned} \begin{array}{c} \varDelta \mathbf {W}_{n} = (\varDelta W^{1}_{n}, \varDelta W^{2}_{n}, \ldots , \varDelta W^{m}_{n})^{T} \sim \mathcal {N}(\mathbf {0}_{m\times m}, h_{n}\mathbf {1}_{m\times m}), \\ \mathbf {V}_{k} = (V^{1}_{k}, V^{2}_{k},\ldots , V^{m}_{k})^{T} \sim \mathcal {N}(\mathbf {0}_{m\times m}, \mathbf {1}_{m\times m}), \\ \mathbf {U}_{k} = (U^{1}_{k}, U^{2}_{k},\ldots , U^{m}_{k})^{T} \sim \mathcal {N}(\mathbf {0}_{m\times m}, \mathbf {1}_{m\times m}). \end{array} \end{aligned}$$

If the programming language supports vectored operations with multidimensional arrays, these formulas can provide a benefit to the performance of the program.

Finally, consider a triple integral. In the only numerical scheme in which it occurs, it is necessary to be able to calculate only the case of identical indexes $\alpha =\beta =\gamma$. For this case,  [32] gives the following formula:

$$ I^{\alpha \alpha \alpha }(h_{n}) = \dfrac{1}{6}\left( (I^{\alpha }(h_{n}))^{3} - 3 I^{0}(h_{n})I^{\alpha }(h_{n})\right) = \dfrac{1}{6}\left( (\varDelta W^{\alpha }_{n})^{3} - 3 h_{n}\varDelta W^{\alpha }_{n}\right) . $$

3.3 Strong and Weak Convergence of the Approximating Function

Before proceeding to the formulation of numerical schemes, it is necessary to determine the criterion of accuracy of approximation of the simulated process $\mathbf {x}(t)$ by the grid function $\mathbf {x}_{n}$. Two criteria are used: weak and strong convergence.

The sequence of approximating functions $\{\mathbf {x}_{n}\}^{N} _ {1}$ converges with order p to the exact solution $\mathbf {x}(t)$ of SDE in moment T in strong sense if constant $C > 0$ exists and $\delta _{0} > 0$ such as $\forall h \in (0,\delta _{0}$ and following condition is fulfilled:

The sequence of approximating functions $\{\mathbf {x}_{n}\}^{N} _ {1}$ converges with order p to the exact solution $\mathbf {x}(t)$ of SDE in moment T in weak sense if constant $C_{F}>0$ exists and $\delta _{0}>0$ such as $\forall h \in (0,\delta _{0}]$ and the following condition is fulfilled:

$$ \left| \mathbb {E}\left[ F(\mathbf {x}(T))\right] - \mathbb {E}\left[ F(\mathbf {x}_{N})\right] \right| \leqslant C_{F}h^{p}. $$

Here $F \in C^{2(p+1)}_{\mathrm {P}}(\mathbb {R},\mathbb {R}^{d})$ is a continuous differentiable functional with polynomial growth.

If the $\mathbf {G}$ matrix is zero, then the strong convergence condition is equivalent to the deterministic case, but the order of strong convergence is not necessarily a natural number and can take fractional-rational values.

It is important to note that the choice of the convergence type depends on the problem one has to solve. Increasing the order of strict convergence leads to more accurate approximation of the trajectories of $\mathbf {x}(t)$. If one wants to calculate, for example, the moment of a random process $\mathbf {x}(t)$ or a generalized functional of the form $\mathbb {E}[F(\mathbf {x}(t))]$, one should increase the order of weak convergence.

4 Stochastic Runge–Kutta-like Numerical Methods

4.1 Euler–Maruyama Numerical Method

The simplest numerical method for solving scalar equations and systems of SDEs is the Euler–Maruyama method, named in honor of Gisiro Maruyama, who extended the classical Euler method for ODEs to the case of equation [23]. The method is easily The each step requires only corresponding to this step increment $\varDelta W^{\beta }_{n}$. The method has a strong order $(p_{d},p_{s}) = (1.0, 0.5)$. The value $p_{d}$ denotes the deterministic accuracy order, when the method is used for the equation with $G(t,x^{\alpha }(t))\equiv 0$. The value $p_{s}$ denotes the order of the stochastic part approximation.

4.2 Weak Stochastic Runge–Kutta-like Method with Order 1.5 for a Scalar Wiener Process

In the case of a scalar SDE, the drift vector $f^{\alpha }(t, x^{\gamma })$ and the diffusion matrix $G^{\alpha }_{\beta }(t, x^{\gamma })$ become f(t, x) and g(t, x) scalar functions, and the driving Wiener process $W^{\beta }_t$ is the scalar $W_t$. For scalar SDE it is possible to construct a numerical scheme with strong convergence $p=1.5$. In the above numerical scheme, the Wiener stochastic process is present in implicit way. It is “hidden” inside the stochastic Ito integrals: $I^{10}(h_{n})$, $I^{1}(h_{n})$, $I^{11}(h_{n})$, $I^{111}(h_{n})$.

4.3 Stochastic Runge–Kutta Method with Strong Order $p=1.0$ for Vector Wiener Process

For SDE system with a multidimensional Wiener process, one can construct a stochastic numerical Runge-Kutta scheme of strong order $p_{s} = 1.0$ by using single and double Ito integrals [31].

Methods SRK1Wm and SRK2Wm have strong order $(p_{d},p_{s}) = (1.0, 1.0)$ and $(p_{d},p_{s}) = (2.0, 1.0)$.

4.4 Stochastic Runge–Kutta Method with Weak Order $p=2.0$ for the Vector Wiener Process

Numerical methods with weak convergence are good for approximation of the distribution characteristics of stochastic process $x^{\alpha }(t)$. The weak numerical method does not need information about the trajectory of driving Wiener process $W^{\alpha }_{n}$ and random increments for these methods can be generated on another probability space. From the paper [15] we get two Butcher tables.

5 Analysis of Implementation Difficulties of Stochastic Runge–Kutta Numerical Methods

As can be seen from the formulas, stochastic Runge-Kutta methods are much more complicated than their classical analogues. In addition to the cumbersome formulas, we can highlight the following factors that complicate the implementation of stochastic methods in software, as well as their application to the numerical solution of SDEs.

• When choosing a particular method, it is necessary to consider what type of convergence is necessary to provide for this problem, as well as which of the stochastic equations should be solved—in Ito or Stratonovich form. This increases the number of algorithms one has to implement.

• For methods with strong convergence greater than one at each step it is necessary to solve the resource-intensive problem of stochastic integrals approximation.

• In the numerical scheme, there are not only matrices and vectors, but also tensors (four-dimensional arrays), it is necessary to perform a convolution operation on several indexes. The implementation of convolution via summation by using normal cycles results in a significant performance drop.

• Weak methods requires the Monte Carlo simulation and, therefore, a large number of repeated computations for the numerical solution. Since the Monte Carlo method converges approximately as 1/$\sqrt{N}$, where N—number of calculations, to achieve an accuracy of at least $10^{-3}$, it is necessary to perform minimum $10^6$ tests.

The most significant performance drop occurs when implementing a universal algorithm, that is, a program that can make a calculation using an arbitrary coefficient table. In this case, we have to use a large number of nested loops in order to organize the summation. The presence of double sums in the schemes as well as complex combination of indices in the multipliers under the sign of these sums complicates the implementation even more and the number of nested cycles increases to six. In addition to these specific features, we mention a few reasons for the performance drop, which also take place in case of deterministic numerical methods. The obvious way to store the coefficients of the methods is to use arrays. However, in explicit methods, that we consider, the matrix is lower-diagonal and storing it as a two-dimensional array results in more than half of the allocated memory being spent on storing zeros.

While examine the source codes of popular routines that implement classical explicit embedded Runge–Kutta methods, one may find that these programs use a set of named constants rather than arrays to store the coefficients of the method. It is also caused by the fact that the operations with scalar variables in most programming languages are faster than operations on arrays.

We wish to preserve the requirement of code flexibility and at the same time to increase the speed of calculations and reduce the memory consumption. That led us to automatic code generation from one template.

In addition to performance gains, automatic code generation allows you to add or modify all functions at once by editing only one template. This allows both to reduce the number of errors and to generate different variants of functions for different purposes.

6 Automatic Code Generation

For code generation we use Python 3 language. The program is open source and available on bitbucket repository by URL bitbucket.org/mngev/sde_num_generation. The repository contains module stochastic. This module implements Wiener stochastic process and the numerical methods we considered in this paper. Most part of the module’s code are generated by scripts from generator directory.

For the code generation, we used Jinja2 [1] template engine. This library was originally developed to generate HTML pages, but it has a very flexible syntax and can be used as a universal tool for generating text files of any kind, including source codes in any programming languages. In addition to Jinja2, we also used NumPy library to work with arrays and speed-up some calculations.

In addition to the two external libraries listed above, the standard fraction module was used. It allows to specify the coefficients of the method as rational fractions, and then convert them to float type with the desired order of accuracy. Also we use typing module to annotate the types of function arguments (Python 3.5 and above feature).

Templates are files with Python source code with insertions of Jinja2 specific commands. Information about the coefficients of the methods is stored separately, in a structured form of JSON format. This makes it easy to add new methods and modify old ones by editing JSON files. Currently we use methods with coefficients presented in [14, 15, 19].

Python itself is used as the language for already generated functions with the active use of NumPy library, which allows to get acceptable performance. However, the generated code can be easily reformatted to match the syntax of any other programming language. We plan to modify the program to generate code in Julia language (julialang.org). This language was introduced in 2012 and initially focused on scientific computing. Currently, he is intensively developing and gaining popularity. To date, the current version is 0.6.2. Julia provides performance comparable to C++ and Fortran, but it is a dynamic language with interactive command line (REPL) capability similar to IPython and can be integrated into an interactive Jupyter environment.

The current version of the library exceeds the one described by the authors in [16]. The use of auto-generation made it possible not to use nested loops, which reduced the number of memory allocations, and greatly simplified the code.

6.1 Realisation of Automatic Code Generation

To study the calculation errors and the efficiency of different stochastic numerical methods, it is necessary to have a universal implementation of such methods. The universality means the possibility to use any stochastic method with a desired strong or weak error by setting its coefficient table. With direct transfer of mathematical formulas to the program code, one need to use about five nested cycles, which extremely reduces performance, since such code does not take into account a large number of zeros in the coefficient tables and arithmetic operations on zero components are still performed, although this is an extra waste of processor time.

One way to achieve versatility and acceptable performance is to generate code for a numerical method step. This approach minimizes the number of arithmetic operations and saves memory, since the zero coefficients of the method do not have to be stored.

We implemented a code generator for the three stochastic numerical methods mentioned above:

• scalar method with strong convergence $p_s = 1.5$,

• vector method with strong convergence $p_s = 1.0$,

• vector method with weak convergence of $p_s = 2.0$.

We use Python to implement the code generator and Jinja2 [1] template engine. This template engine was originally created to generate HTML code, but its syntax is universal and allows you to generate text of any kind without reference to any programming or markup language.

Information about the coefficients of each particular method is stored as a JSON file of the following structure:

The parameter stage is the number of method’s stages, det_order is the error order of the deterministic part ($p_d$), stoch_order is the error order of the stochastic part ($p_s$), name is the name of the method, which will then be used to create the name of the generated function, so it should be written in one word without spaces. All other parameters are the coefficients of the method. In this case, we give the coefficients of the scalar method with strong convergence $p_s=1.5$, omitting the coefficients $\mathbf {a}_{0}$, $\mathbf {a}_{1}$ and $\mathbf {B}_{0}$ to save text space. It is necessary to note that the values of the coefficients can be specified in the form of rational fractions, for which they should be presented as JSON strings and enclosed in double quotes.

For internal representation of stochastic numerical methods we created three Python classes: ScalarMethod, StrongVectorMethod and WeakVectorMethod. The implementation of these classes is contained in the file coefficients_table.py. The constructors of these classes read the JSON file and, based on them, create objects, which can later be used for code generation. The Fraction class from the Python standard library is used to represent rational coefficients. Each class has a method that generates a coefficient table in format.

The file stoch_rk_generator.py is a script which handles the jinja2 templates and, based on them, generates a code of python functions. For vector stochastic methods, a code is generated for dimensions up to 6. Functions are named based on the information specified in JSON files, such as strong_srk1w2, strong_srk2w5, weak_srk2w6, and so on.

In addition to the code in Python, formulas are generated. It allows one to check the correctness of the generator. For example, we give below the formula generated automatically based on the data from JSON file for Runge–Kutta method strong_srk1w2 with stages $s = 3$, and 2 dimensioned Wiener process. Nonzero coefficients of the method are as follows:

$$\begin{aligned} \begin{array}{c} A_{01}^2 = 1,\; A_{11}^2 = 1,\; A_{11}^3 = 1,\; B_{11}^2 = 1,\; B_{11}^3 = -1,\\ a_1 = 1/2,\; a_2 = 1/2,\; c_{0}^2 = 1,\; c_{1}^2 = 1,\; c_{1}^3 = 1,\; b^{1}_1 = 1,\; b^{2}_2 = 1/2,\; b^{2}_3 = -1/2. \end{array} \end{aligned}$$

7 Parallel SDE Integration with Weak Numerical Methods

Stochastic numerical methods with strong convergence are well suited for computing a specific trajectory of SDE solution. If we are not interested in a specific trajectory, but in some probabilistic characteristics (distribution of a random process, mathematical expectation, variance, etc.), then we should use numerical methods with weak convergence.

In the case of numerical methods with weak convergence, we have to use Monte Carlo method. It means that we should solve our SDE system multiple times and each time with different trajectory. The error of the Monte Carlo method depends on the number of trials N as $\sqrt{N}$, so to achieve the accuracy of $10^{-3}$ we need $10^{6}$ trials. However, since the trajectories of the Wiener process are independent, the SDE for each specific trajectory can be solved independently in parallel mode.

We have implemented a script in Python, which allows to find solutions of SDE for N different trajectories in parallel mode by spawning a given number of processes. For processes spawning we use multiprocessing module. The following features of the Cpython interpreter should be noted.

• Because of the global interpreter lock (GIL), it is not possible to use threads for the Monte Carlo method. The standard threading module is only suitable for asynchronous tasks.

• When using processes, you should reinitialize the random number generator with new seed for each process separately, because otherwise all generated processes will generate the same sequence of random numbers.

The source code of the implemented script is located in the tests directory. It is based on two functions.

• Function calculation performs the necessary calculations for a given number of trajectories. As arguments, the function takes the drift vector, the diffusion matrix, the required number of simulations, the initializing value for the random generator, the initial value of the SDU solution, the number of steps of the Wiener process, the time interval at which it is necessary to carry out integration, the dimension of the Wiener process and optionally the function for testing the obtained solution for adequacy.

• Function run_parallel distributes the Monte Carlo tests equally between processes, creates a pool of processes, and runs them. Each process performs the function calculation.

When carrying out a large number of tests, the storage of all the resulting trajectories requires a significant amount of RAM. Therefore, it is more reasonable to immediately decide what probabilistic characteristics we need and calculate them using on-line algorithms. For example, to calculate the average trajectory, we use the following formula

$$ \bar{\mathbf {x}}_{n} = \bar{\mathbf {x}}_{n-1} + \dfrac{\mathbf {x}_n - \bar{\mathbf {x}}_{n-1}}{n}. $$

This formula allows you to update the mean values of all path steps $\bar{\mathbf {x}}_{n}$ based on the previous mean values $\bar{\mathbf {x}}_{n-1}$ and the current value $\mathbf {x}_n$. As a result, each process must store only one array of constant length, which saves memory.

8 Conclusion

Stochastic numerical schemes with convergence order higher than 0.5 are considered. It is shown that such methods are much more complicated than equivalent numerical methods for systems of ordinary differential equations. Their specifics makes efficient software implementation of such methods not a trivial task. We discuss an approach based on automatic generation of code, which allows to obtain an efficient implementation of the methods and gives the possibility to use any table of coefficients. We also give a short description of our program and provide the url link to the repository with the source code.