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}\]

or

\[ \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:

[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

  • 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).