NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, VOL., 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