Continuous-Time Random Walk¶

Base Class¶

Warning

doxygenclass: Cannot find class “mocca::CTRWbase” in doxygen xml output for project “mocca” from directory: doxygen/xml/

Solver (Full)¶

template<typename MatType, int Flags, typename RandomEngine> class CTRW : public mocca::internal::Solver<CTRW<MatType, Flags, RandomEngine>>, public mocca::CTRWBase<MatType, Flags, RandomEngine>¶

A solver based on continuous-time random walks for computing the matrix exponential \( \exp(\mathbf{A}t) \) and Mittag-Leffler function \( ML_{\alpha}(t^\alpha \mathbf{A}) \) with \( 0 < \alpha \leq 1 \), which is is defined as the following series

\[ ML_\alpha(\mathbf{A}) = \sum_{k = 0}^{\infty}{\frac{\mathbf{A}^k}{\Gamma(\alpha z + 1)}} \]

For \(\alpha = 0\), the Mittag-Leffler function is reduced to the exponential function.

After initializing the solver with the desired parameters and setting the input matrix, call expm() or mittag_leffler() to calculate the matrix exponential and Mittag-Leffler function, respectively.

See the following papers for more information:

[1] J. A. Acebrón, ‘A Monte Carlo method for computing the action of a matrix exponential on a vector’, arXiv:1904.12759 [cs, math], Jun. 2019, [Online]. Available: http://arxiv.org/abs/1904.12759

[2] J. A. Acebrón, J. R. Herrero, and J. Monteiro, ‘A highly parallel algorithm for computing the action of a matrix exponential on a vector based on a multilevel Monte Carlo method’, arXiv:1904.12754 [cs, math], Jul. 2019, [Online]. Available: http://arxiv.org/abs/1904.12754

Template Parameters:

MatType - Matrix Type, must be either a CSRMatrix or Matrix
Flags - Additional flags for the solver. See MonteCarloFlags for more information.
RandomEngine - Type of the Random Number Generator

Warning

The input matrix must not contain zeroes in the diagonal, or this method will fail.

Public Functions

inline CTRW(CTRWOptions param = CTRWOptions())¶

Initialize the CTRW solver with param parameters. Complexity: Constant

Parameters:: param – [in] parameters of the solver (see CTRWOptions for all available param)

inline CTRW(MatType &A, CTRWOptions param = CTRWOptions())¶

Initialize the CTRW solver with param parameters and input matrix A for further computing the matrix exponential or Mittag-Leffler function.

Complexity: Constant

Parameters:

A – [in] input matrix
param – [in] parameters of the solver (see CTRWOptions for all available options)

inline index_t rows() const¶

Returns:: the number of rows of the underlying matrix

inline index_t cols() const¶

Returns:: the number of cols of the underlying matrix

inline expm_evaluator expm(value_type time)¶

Calculates the matrix exponential.

Parameters:: time – [in] time parameter t

inline ml_evaluator mittag_leffler(value_type alpha, value_type time)¶

Calculates the Mittag-Leffler function.

Parameters:

alpha – [in] parameter alpha of the Mittag-Leffler function
time – [in] time parameter t

Solver (Action)¶

template<typename MatType, SamplingType Sampling, int Flags, typename RandomEngine> class CTRWAction : public mocca::internal::Solver<CTRWAction<MatType, Sampling, Flags, RandomEngine>>, public mocca::CTRWBase<MatType, Flags, RandomEngine>¶

A solver based on continuous-time random walks for computing the action of the matrix exponential \( \exp(\mathbf{A}t) \) and Mittag-Leffler function \( ML_{\alpha}(t^\alpha \mathbf{A}) \) over a vector. In mathematical terms, for a vector \(\vec{v}\) and \(t > 0\), this solver calculates

\[\vec{x} = \exp(\mathbf{A}t)\ \vec{v}\]

\[ \vec{x} = ML_{\alpha}(t^\alpha \mathbf{A})\ \vec{v} \text{ for } 0 < \alpha \leq 1 \]

where

\[ ML_\alpha(\mathbf{A}) = \sum_{k = 0}^{\infty}{\frac{\mathbf{A}^k}{\Gamma(\alpha z + 1)}} \]

For \(\alpha = 0\), the Mittag-Leffler function is equal to the exponential function.

There are two ways to compute the random walks: forward (i.e., \( 0 \rightarrow t \)) or backward in time (i.e., \( t \rightarrow 0 \)). Backward sampling is usually more accurate if v have only a few entries (preferentially, stored as a SparseVector) or contains some entries that have much larger value than the others. However, this requires that the matrix A be transposed beforehand (this will be done automatically by the solver) and force the solver to calculate the entire solution (in this case, first_row and last_row do nothing). Forward sampling, on the other hand, allows the computation of just a couple of entries in the solution vector.

After initializing the solver with the desired parameters and setting the input matrix, call expm() or mittag_leffler() to calculate the action of the matrix exponential and Mittag-Leffler function over the target vector, respectively.

See the following papers for more information:

Template Parameters:

MatType - Matrix Type, must be either a CSRMatrix or Matrix
Sampling - Either kBackwardSampling or kForwardSampling
Flags - Additional flags for the solver. See MonteCarloFlags for more information.
RandomEngine - Type of the Random Number Generator

Warning

The input matrix must not contain zeroes in the diagonal, or this method will fail.

Public Functions

inline CTRWAction(CTRWOptions param = CTRWOptions())¶

Initialize the CTRWAction solver with param parameters.

Complexity: Constant

Parameters:: param – [in] parameters of the solver (see CTRWOptions for all available options)

inline CTRWAction(MatType &A, MatrixStructure symmetry = kGeneric, CTRWOptions param = CTRWOptions())¶

Initialize the CTRWAction solver with param parameters and input matrix A for further computing the action of the matrix exponential or Mittag-Leffler over a vector. If kBackwardSampling was selected, this will transpose the matrix A.

Complexity: Linear in A.size() if Type == kBackwardSampling. Constant, otherwise.

Parameters:

A – [in] input matrix
param – [in] parameters of the solver (see CTRWOptions for all available options)

virtual ~CTRWAction() = default¶: Default Destructor.

inline index_t rows() const¶

Returns:: the number of rows of the underlying matrix

inline index_t cols() const¶

Returns:: the number of cols of the underlying matrix

inline void set_matrix(MatType &A, MatrixStructure symmetry = kGeneric)¶

Initialize the CTRWAction solver with the matrix A for further computing the action of the matrix exponential or Mittag-Leffler over a vector. If kBackwardSampling was selected, this will transpose the matrix A.

Complexity: Linear in A.size() if Type == kBackwardSampling. Constant, otherwise.

Parameters:: A – [in] input matrix

inline expm_evaluator<Vector<value_type>> expm(value_type time, Vector<value_type> &v)¶

Calculates the action of the matrix exponential over the vector.

Parameters:

time – [in] time parameter t
v – [in] input vector

Returns:

an abstract object representing the action of \( \exp(\mathbf{A}t) \) over the vector v.

inline ml_evaluator<Vector<value_type>> mittag_leffler(value_type alpha, value_type time, Vector<value_type> &v)¶

Calculates the action of the Mittag-Leffler function over the vector.

Parameters:

alpha – [in] alpha of the Mittag-Leffler function
time – [in] time parameter t (default: 1)
v – [in] vector

Returns:

an abstract object representing the action of \( ML_{\alpha}(t^\alpha \mathbf{A}) \) over the vector v.

Options¶

struct CTRWOptions¶

Options for all routines based on continuous-time random walks (CTRW).

Public Members

index_t num_samples = 1E6¶: The number of random samples.

uint64_t seed = PCG32_DEFAULT_SEED¶: Indicate the random seed for the random number generator (PCG64).

uint64_t stream = PCG32_DEFAULT_STREAM¶: Indicate the random stream of the random number generator (PCG64).