NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, VOL.25, e2158, 2018.  

TITLE: On Compact Vector Formats in the Solution of the Chemical Master 
Equation with Backward Differentiation 

AUTHORS: Tugrul Dayar and M. Can Orhan  

ABSTRACT: A stochastic chemical system with multiple types of molecules 
interacting through reaction channels can be modeled as a continuous-time 
Markov chain with a countably infinite multidimensional state space. 
Starting from an initial probability distribution, the time evolution of 
the probability distribution associated with this continuous-time Markov 
chain is described by a system of ordinary differential equations, known 
as the chemical master equation (CME). This paper shows how one can solve 
the CME using backward differentiation. In doing this, a novel approach 
to truncate the state space at each time step using a prediction vector 
is proposed. The infinitesimal generator matrix associated with the 
truncated state space is represented compactly, and exactly, using a sum 
of Kronecker products of matrices associated with molecules. This exact 
representation is already compact and does not require a low-rank 
approximation in the hierarchical Tucker decomposition (HTD) format. 
During transient analysis, compact solution vectors in HTD format are 
employed with the exact, compact, and truncated generated matrices in 
Kronecker form, and the linear systems are solved with the Jacobi method
using fixed or adaptive rank control strategies on the compact vectors. 
Results of simulation on benchmark models are compared with those of the 
proposed solver and another version, which works with compact vectors
and highly accurate low-rank approximations of the truncated generator 
matrices in quantized tensor train format and solves the linear systems 
with the density matrix renormalization group method. Results indicate
that there is reason to solve the CME numerically, and adaptive rank 
control strategies on compact vectors in HTD format improve time and 
memory requirements significantly.

KEY WORDS: Backward differentiation, chemical master equation, compact 
vector, continuous-time Markov chain, Kronecker product