Direct Solution of the Chemical Master Equation Using Quantized Tensor Trains

By Vladimir A. Kazeev, Mustafa Hani Khammash, Michael Nip, Christoph Schwab. 2014

177 citations recorded by the source corpus.

The Chemical Master Equation (CME) is a cornerstone of stochastic analysis and simulation of models of biochemical reaction networks. Yet direct solutions of the CME have remained elusive. Although several approaches overcome the infinite dimensional nature of the CME through projections or other means, a common feature of proposed approaches is their susceptibility to the curse of dimensionality, i.e. the exponential growth in memory and computational requirements in the number of problem dimensions. We present a novel approach that has the potential to “lift” this curse of dimensionality. The approach is based on the use of the recently proposed Quantized Tensor Train (QTT) formatted numerical linear algebra for the low parametric, numerical representation of tensors. The QTT decomposition admits both, algorithms for basic tensor arithmetics with complexity scaling linearly in the dimension (number of species) and sub-linearly in the mode size (maximum copy number), and a numerical tensor rounding procedure which is stable and quasi-optimal. We show how the CME can be represented in QTT format, then use the exponentially-converging -discontinuous Galerkin discretization in time to reduce the CME evolution problem to a set of QTT-structured linear equations to be solved at each time step using an algorithm based on Density Matrix Renormalization Group (DMRG) methods from quantum chemistry. Our method automatically adapts the “basis” of the solution at every time step guaranteeing that it is large enough to capture the dynamics of interest but no larger than necessary, as this would increase the computational complexity. Our approach is demonstrated by applying it to three different examples from systems biology: independent birth-death process, an example of enzymatic futile cycle, and a stochastic switch model. The numerical results on these examples demonstrate that the proposed QTT method achieves dramatic speedups and several orders of magnitude storage savings over direct approaches.

Subfields: Computational Mathematics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Theory and Mathematics

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “…PDEs [30,113]; • the solution of the Boltzmann equation [129, 149], and the chemical master / Fokker-Planck equations [4,6,61,64,86,122,133,135,196] • the solution of high-dimensional Schr¨odinger equations [46,160,172,184,192,193]; • computational tasks in micromagnetics [80,81]; •…”
ALTERNATING MINIMAL ENERGY METHODS FOR LINEAR SYSTEMS IN HIGHER DIMENSIONS∗ (2014, methodology): “For some systems with moderate dimensions and small time steps, the DMRG method can be of good use, as was demonstrated in [29].”
Multilevel preconditioning and low‐rank tensor iteration for space–time simultaneous discretizations of parabolic PDEs (2015, methodology): “The second approach [23, 24, 25, 26, 27] are the DMRG or (M)ALS methods, which work directly within the structure of the low rank tensor format, typically the hierarchical Tucker or the Tensor Train format.”
Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 1 Low-Rank Tensor Decompositions (2016, unknown): “5 Links between TNs and Machine Learning models Table 4 summaries the connections of tensor networks with graphical and neural network models in machine learning and statistics [54,55,64,65,138,192,198, 285].”
Alternating Minimal Energy Methods for Linear Systems in Higher Dimensions (2013, unknown): “For some systems with moderate dimensions and small time steps, the DMRG method can be of good use, as was demonstrated in [29].”