WorksComputer Science
A Multigrid Finite State Projection Algorithm For The Solution Of The Reaction-Diffusion Master Equation
Abstract
We develop a multigrid method for the finite state projection of the reaction-diffusion master equation (RDME). The RDME evolves the joint probabilities of molecular count configurations across well-mixed voxels coupled by local reactions and diffusive jumps. When fast diffusion or large reaction rates make this evolution stiff over long time horizons, implicit time stepping requires solving a large shifted linear system at every step. Grouping neighboring voxels and summing their molecular counts produces a hierarchy of coarser state spaces terminating at a one-voxel chemical master equation. Restriction sums residual entries with the same coarse counts, while multinomial prolongation preserves the RDME generator form on every level with explicit coarse reaction and diffusion rates. For reversible diffusion, the error omitted by coarsening is bounded by the graph Dirichlet energy of jumps inside the aggregates, with a constant independent of population. Numerical tests with standard multigrid cycles and point or block Gauss-Seidel smoothing reach 7.16 million states and resolve rare probabilities of order .
Introduction
The reaction-diffusion master equation (RDME) models stochastic chemical reactions and diffusion through the probabilities of discrete molecular counts [10, 16]. The spatial domain is partitioned into well-mixed cells, called voxels, and a state specifies the integer copy number of each chemical species in each voxel. Molecules react locally within voxels and jump between neighboring voxels by diffusion. Because the master equation assigns a separate probability unknown to every reachable arrangement of molecules across the grid, even a small spatial domain can produce a large state space. Finite state projection (FSP) retains a finite subset of configurations and treats transitions leaving that subset as absorbing losses [19], yielding a finite linear evolution equation .
When fast diffusive jumps or large reaction propensities make this evolution stiff over long time horizons, advancing the FSP probability vector with an implicit time integrator requires solving a shifted linear system at every step. Although the generator is sparse, the transition graph on molecular count configurations has much higher connectivity than a physical mesh, and sparse direct factorization can require far more memory than the matrix and solution vector themselves. Multigrid methods avoid this factorization bottleneck by combining local relaxation with corrections computed on a hierarchy of smaller linear systems [5, 27].
Past Work
Several numerical representations reduce the cost of integrating the chemical master equation, including adaptive discrete Galerkin approximations [9], sparse grids [14], quantized tensor train decompositions [17], and state aggregation [13]. Multigrid and multilevel aggregation methods for Markov chains have primarily targeted stationary distributions through multiplicative or additive coarse corrections on the transition graph [8, 26]. Our solver instead addresses the shifted linear systems arising in implicit FSP time integration, pairing voxel aggregations gation with standard V-, W-, and K-cycles [20, 27] and point or block Gauss–Seidel smoothing [21].
Contributions
We construct a multigrid method for the finite RDME equations using groups of physical voxels to determine the coarse states. Because each fine unknown belongs to a complete spatial arrangement of molecules rather than to a single spatial node, spatial coarsening must also specify how probability entries are restricted and prolonged across compatible arrangements. The contributions of this paper are as follows.
We construct successive coarse state spaces by grouping neighboring voxels and summing their molecular counts, terminating at a chemical master equation (CME) on one voxel. Restriction sums residual entries sharing the same coarse counts, and prolongation distributes coarse corrections among compatible fine arrangements using multinomial weights. These transfers supply additive corrections to the fine probability vector, which remains the numerical solution throughout the iteration.
We derive closed-form coarse reaction and diffusion propensities by averaging fine transitions under the multinomial weights. The Galerkin coarse operator retains the reaction-diffusion generator structure and absorbing boundary losses, allowing the same construction to be repeated at every level without explicit sparse matrix multiplication.
For reversible diffusion, we bound the error omitted by the coarse representation in terms of a weighted Dirichlet energy on the graph of molecular arrangements. The resulting approximation constant is independent of the molecular population for fixed aggregates and jump rates, whereas a convergence bound for the full cycle would also require estimates for smoothing and recursive coarse solves.
We examine convergence under population and spatial refinement and compare the computational cost of standard cycles with point and block Gauss–Seidel smoothing. Transient integrations reach 7.16 million retained states, and a calculation of rare switching between metastable states resolves an endpoint probability of order that remains poorly sampled across 60 million independent trajectories of the stochastic simulation algorithm (SSA).
The coarse counts do not generally evolve as an autonomous Markov chain [18], because nonlinear reaction propensities depend on how molecules are distributed among the constituent fine voxels. The coarse equations therefore serve strictly to compute corrections for the fine linear system rather than to replace the fine evolution.
Section 2 introduces the state probabilities, finite state projection, and implicit time discretization. Section 3 presents the multigrid hierarchy, transfer operators, smoothers, and time-integration algorithms. Section 4 states the Galerkin rate theorem and the approximation and residual bounds, with complete proofs given in Appendix A. The numerical experiments in Section 5 address the specified RDME rather than its continuum limit as voxel volume vanishes [16, 15]. The supplementary material contains a worked two-voxel calculation, additional multilevel analysis, validation checks, implementation measurements, and an SSA study of a propagating spatial front.
States and Probability Equations
We begin with molecular counts in a well-mixed reaction compartment and then introduce a separate count for each species in each voxel. Finite state projection selects the states whose probabilities are evolved, and implicit time discretization produces the shifted linear systems solved by multigrid.
The RDME on One Voxel
On one well-mixed voxel of volume , the RDME reduces to the chemical master equation (CME). Consider chemical species in a well-mixed volume . A state records their molecular counts,
Let be the probability of state at time and collect these probabilities into the vector . A state has integer coordinates, whereas the probability vector has one entry for every admissible combination of counts, including states that carry zero probability initially. Each chemical reaction alters the molecular counts and induces a linear probability flux between the corresponding entries of .
In reaction channel , let and denote the numbers of molecules of species consumed and produced, respectively, and let be the rate constant. Writing and , the reaction channel and its mass-action propensity are
The propensity is the transition rate from state to state . Here is the reaction order, and the binomial factors count the distinct combinations of reactant molecules available in state [12], with combinatorial rate factors absorbed into .
The probability flux through reaction out of state is the product . Summing incoming fluxes from predecessor states and subtracting outgoing fluxes gives the master equation
where terms with negative molecular counts are omitted. Although the propensities depend nonlinearly on the counts when , the balance (2) is linear in the probabilities. Enumerating the states as and letting gives the matrix equation
where is the vector of ones and is the Markov generator. Column of collects the outgoing transitions from source state , with entries
The off-diagonal entries are nonnegative transition rates, and each diagonal entry equals the negative sum of the off-diagonal entries in its column so that total probability is conserved.
The RDME on Multiple Voxels
The spatial RDME retains the linear probability balance of (2) while assigning each species a separate count in every voxel.
Consider an undirected graph of well-mixed voxels with positive volumes . Since each voxel contains the same species, a spatial state is the count array
The probability belongs to this complete array, whose rows specify the molecular counts in individual voxels. Summing over all rows except row yields the marginal distribution in voxel , but these voxel marginals do not form a closed system when nonlinear reactions are present. The RDME evolves the joint distribution over all reachable arrays (4).
Local reactions act on a single row of (4). Reaction in voxel changes to for each species while leaving all other rows unchanged, with propensity
Diffusive jumps couple two adjacent rows by transferring one molecule of species from voxel to a neighboring voxel . Each directed edge and species gives the first-order transition acting on by
The reverse jump from to occurs at rate per molecule, which may differ from when voxel volumes are unequal. Summing the reaction and diffusion fluxes according to (2) gives the spatial master equation . Each configuration has integer coordinates, and every elementary reaction or diffusion event connects two configurations. With a single voxel there are no diffusive jumps, and the RDME reduces to the CME.
Finite State Projection
When open reactions allow molecular counts to grow without bound, we select a finite state set and evolve its probability entries by the finite state projection [19]. In our multigrid construction, retention is specified by the species totals . All spatial arrangements sharing the same totals form a population block, and is chosen as a finite union of complete population blocks. Because diffusive jumps conserve every species total , no diffusion transition can leave . Only reaction channels that change the species totals can cross the truncation boundary. For one species truncated at maximum population , the retained state space is
Bounding the total population rather than capping each voxel count separately makes closed under diffusion. Restricting the generator to the principal submatrix on these states gives the finite evolution equation
where and henceforth denote the retained generator and probability vector. Omitting a destination state outside removes its off-diagonal entry while leaving its outgoing rate in the source diagonal entry , so escaping probability mass is absorbed rather than reflected to a boundary state.
For a nonexplosive Markov chain whose initial distribution is supported in , the exact solution of (7) extended by zero outside has truncation error [19]. This missing mass measures truncation of the continuous-time chain independently of the additional errors from time stepping and iterative linear solves. When a fixed cap is insufficient over long integrations, adaptive FSP enlarges by appending complete population blocks and retries a rejected step from the previous distribution, as detailed in Supplementary Section S3.2.
Time Discretization
We integrate the finite evolution equation (7) by solving a shifted linear system at each time step. Let for step size . Both backward Euler and Crank–Nicolson advance to by solving
where the shift and right-hand side are given by
Here lowercase denotes a vector on , while uppercase denotes a molecular count configuration. Because has nonnegative off-diagonal entries and nonpositive column sums, is a nonsingular -matrix with column sums bounded below by . Each iterative solve starts from the preceding distribution and applies multigrid cycles until the residual meets the stopping tolerance. For Crank–Nicolson integrations, we replace the first interval by two backward Euler half-steps of size . Both half-steps and the subsequent Crank–Nicolson steps share the shift , allowing the assembled level matrices and relaxation factors to be reused across steps.
The Multigrid Method
At each time step, multigrid solves (8) by adding corrections to an approximate fine probability vector . The discrepancy of in (8) is the residual , and the unknown algebraic error satisfies the residual equation
Although is unknown, the residual is directly computable from , , and . Multigrid approximates by combining local relaxation on the fine space with corrections computed on a hierarchy of coarser state spaces.
To motivate the choice of coarse spaces, consider the diffusion generator inside , whose transitions connect molecular arrangements sharing the same species totals. When the diffusive jump rates are reversible with respect to voxel volumes, admits positive equilibrium weights on each population block satisfying . Section 4.2 constructs these weights explicitly from the voxel volumes without assuming equilibrium for the reacting system. Because the equilibrium weights vary across arrangements, we measure smoothness of an error vector through its relative entries . The associated graph Dirichlet energy and weighted norm are
This graph energy is small when the relative error varies slowly across diffusive jumps. For an eigenmode of , its graph energy divided by equals its decay rate under pure diffusion, so modes with a small energy ratio decay slowly and form the analogue of smooth geometric modes for the probability equation.
Our coarse spaces group neighboring voxels into aggregates and retain their combined molecular counts, representing errors whose relative entries vary little among arrangements that share the same aggregate counts. Relaxation supplies fine updates within each aggregate class that cannot be represented through coarse counts alone. § 1.4.2 bounds the approximation error omitted by coarsening in terms of the portion of (10) coming from diffusive jumps inside the aggregates.
Repeating the voxel aggregation recursively reduces the grid until a single voxel remains. A multigrid cycle descends through the hierarchy by applying forward relaxation followed by residual restriction. At the bottom level, the shifted CME on one voxel is solved directly to obtain a coarse correction. The cycle then ascends through the hierarchy, prolonging and adding each correction before applying reverse relaxation at every level. Throughout the cycle, the fine probability vector remains the primary numerical unknown, and the coarse equations serve solely to accelerate the fine linear solve.
Sections 3.1–3.4 introduce the coarse states, transfer operators, and Galerkin coarse equations. Sections 3.5–3.8 describe the smoothers, cycle recursions, stopping rule, and complete time-integration algorithms. Figure 1 illustrates the state hierarchy and a single V-cycle, and Supplementary Section S1 presents a worked two-voxel calculation.

Figure 1. Hierarchy for one species from a four-voxel RDME to a one-voxel CME. (a) Heavy outlines group voxels for the next aggregation, and dots are molecules. The 10 arrangements of two molecules map to 3 coarse states and then the single CME state . Restriction sums vector entries over each shaded group. (b) A V-cycle relaxes and restricts the residual on descent, solves the correction equation directly at the bottom, and prolongs the correction with reverse relaxation on ascent. State counts are those of the Schlögl test in § 1.5.2 at cap 80.
Coarse States and Restriction
Restriction groups fine states by their molecular counts on aggregated voxels and sums the corresponding vector entries. Consider a partition of the voxel graph into disjoint connected groups , called aggregates. Each aggregate forms one coarse voxel with volume and species counts
Let denote the resulting coarse configuration and let denote the coarse state space, with dimension . Enumerating the fine and coarse states as and , two fine states map to the same coarse state whenever their aggregate counts agree, regardless of how the molecules are arranged inside each aggregate. The restriction matrix acts by
Applied to a fine probability distribution , restriction computes the exact coarse marginal distribution . Within a multigrid cycle, acts on the fine residual , summing its signed entries over each coarse equivalence class.
Summing counts over each aggregate preserves the global species totals while removing distinctions between internal voxel arrangements. The construction permits any partition into connected aggregates, and our Cartesian experiments group adjacent voxels in dimensions.
Prolongation to Fine Arrangements
To distribute a coarse correction among fine arrangements with prescribed aggregate counts, we place the molecules of species in aggregate independently across its constituent voxels, choosing with probability . These volume fractions give uniform expected concentration across the voxels of each aggregate. Multiplying the placement probabilities by the multinomial count of indistinguishable permutations gives, for fine state and coarse state , the prolongation weight
and otherwise. The weight factors across aggregates and species because their placements are independent. § 1.4.2 shows that equals the diffusion equilibrium probability conditioned on the aggregate counts when the jump rates satisfy detailed balance with the voxel volumes. For a coarse vector , prolongation acts by
Each column of contains a single nonzero entry equal to one, and each row of contains a single nonzero entry equal to its multinomial weight .
Because the transfer operators preserve species totals, ordering states by total population and then grouping fine states by their coarse image puts both matrices into block-diagonal form. Letting denote the column vector of multinomial weights (13) for fine states in class , this ordering gives
In each block , the row vector sums the entries of the compatible fine arrangements, and the column vector distributes the coarse correction across them with , as illustrated in Figure 2.

Figure 2. The transfer operations for one species with coarse state at index on four voxels of equal volume with aggregates and . Dots are molecules and heavy outlines are aggregates. (a) Restriction sums the residual entries of the three fine arrangements with these counts. (b) Prolongation distributes the coarse correction by the multinomial weights (13) and adds it to the fine iterate.
Because each fine state belongs to a unique coarse class and the weights in each column of sum to unity by the multinomial theorem, the transfer operators satisfy
where each vector has compatible dimension. Restriction therefore recovers any prolonged coarse vector, and makes a projection on the fine space.
Coarse Correction
A coarse-level correction has the prolonged form , and its action on the restricted residual is . Requiring this term to cancel the restricted residual determines the Galerkin coarse system and fine update
The coarse correction has signed entries. An exact coarse solve annihilates the restricted residual,
so the updated iterate satisfies the fine equation after summation over each coarse count class. Because implies , the update also preserves the fine component omitted by restriction,
adding a coarse correction without replacing the fine iterate by a multinomial distribution. Relaxation damps error components in the null space of before and after (17).
Coarse Equations
To apply (17) recursively across multiple levels, we assemble the Galerkin coarse generator
For distinct coarse states , expanding the matrix product shows that averages all fine transition rates leading from class to class ,
Evaluating these averages analytically yields closed-form coarse diffusion and reaction propensities without forming the sparse matrix product .
For diffusion (suppressing the species index), a molecule in aggregate occupies fine voxel with marginal probability under (13), so its expected jump rate per molecule into another aggregate () is
with coarse diffusive propensity . Diffusive jumps between fine voxels inside the same aggregate leave the coarse counts unchanged and cancel between off-diagonal and diagonal entries. On a uniform -dimensional Cartesian grid of spacing and jump rate coarsened by grouping voxels per aggregate, adjacent aggregates share fine interface edges with , so (21) gives , which is twice the naive coarse finite-difference rate .
If the reaction rate constant is uniform across the fine voxels of aggregate , the corresponding coarse reaction propensity is
Theorem 4.1 proves that (21) and (22), together with absorbing losses at omitted destination states, reproduce the Galerkin generator .
Because retains the algebraic form of an RDME generator on the aggregate voxel graph, repeating the construction across coarsening steps gives the level generators
provided each reaction rate constant is uniform within every aggregate at every level. The bottom level has a single voxel of volume and no diffusion, reducing to a well-mixed CME on the species totals with unknowns for one species at cap . By (16), the shifted coarse operators satisfy
so the same generator hierarchy applies at every positive shift .
Smoothing
Because a coarse correction lies in the column space of , it cannot independently adjust relative errors among fine arrangements that share the same coarse counts. Relaxation sweeps on supply these local updates before and after coarse correction. We apply point or approximate block Gauss–Seidel to the complete shifted matrix , including reactions, diffusion, absorbing losses, and the shift. Point Gauss–Seidel updates one state component at a time via
using each updated entry immediately in subsequent rows. The default point smoother applies two forward sweeps before coarse correction and two reverse sweeps afterward.
Updating an entire population block simultaneously accounts for the diffusive coupling among all arrangements of that total population. For a single species with birth and death reactions that change the molecule count by one, diffusion preserves the total population while reactions change by , so ordering states by makes block tridiagonal. Letting and denote the subvectors for population , approximate block Gauss–Seidel updates each population block in turn via
where is the zero-fill incomplete LU factorization, denoted ILU(0), of the diagonal block [21] and indices outside are omitted. The default block smoother applies one forward sweep before coarse correction and one reverse sweep afterward. On the bottom CME level , each population block is a scalar entry, and the resulting tridiagonal matrix is factored once in linear time. For multi-species models, point relaxation and a sparse direct bottom solver can be used without changing the transfer operators.
Because smoothing is separate from restriction, coarse solution, and prolongation, replacing the smoother leaves , , and unchanged. For example, cascading smoothers [23] could be constructed for these shifted systems and applied at the same points in the cycle.
Multigrid Cycles
A multigrid cycle combines relaxation on level with a recursive coarse correction on level . Let denote one cycle for starting from a zero initial guess, where . After forward relaxation of on level and restriction of the residual , the V- and W-cycles compute by
performing one recursive step () in a V-cycle and two recursive steps () in a W-cycle [27].
The K-cycle instead minimizes the coarse residual norm over at most two recursive directions [20]. It first scales the initial recursive direction to minimize the coarse residual norm along . If this scaled correction reduces the coarse residual norm by at least a factor of four, it is accepted without a second call. Otherwise, the cycle computes a second recursive direction on the remaining residual and chooses the optimal linear combination of both directions, as detailed in Supplementary Section S2.1. At the bottom level , the direct CME solve replaces this procedure. Because the optimal weights depend on the residual, the K-cycle is nonlinear and is applied directly as a standalone solver, whereas the linear W-cycle is used when preconditioning GMRES [22].
Accuracy and Computational Cost
At each time step, we initialize from the preceding probability distribution and apply
until . Proposition 4.4 shows that this stopping rule bounds the algebraic error by using only the computable fine residual. Time discretization and FSP truncation errors are assessed separately.
Applying or requires work, and a point sweep or an application of stored ILU(0) factors requires work. For one species on a -dimensional Cartesian hierarchy at fixed cap , summing this work across levels yields cost per V-, W-, or K-cycle when , with an additional logarithmic factor for W- and K-cycles when (Supplementary Section S2.3). Level matrices and ILU(0) factors are reused while is unchanged, and existing diagonal blocks are preserved when adaptive FSP increases (Supplementary Section S3.2). Optional reduction under reflection symmetry is described in Supplementary Sections S4.3 and S4.4.
Algorithms
Algorithm 3.1 summarizes the implicit time integration loop, Algorithm 3.2 specifies the recursive multigrid cycle, and Algorithms 3.3–3.5 give the construction and application of the transfer operators.
The implementation stores two arrays of length on each level rather than sparse transfer matrices. For fine state , parent[i] records the coarse index of , and weight[i] stores its multinomial weight , encoding
with all other entries zero. Algorithm 3.3 builds these arrays once during setup, evaluating factorials through their logarithms and normalizing each column of to unity. While the permutation in (15) illustrates the block structure, the solver retains its population and lexicographic voxel ordering on every level, as shown in Supplementary Figures S1 and S2.
Algorithm 3.1 Advance the RDME probability distribution in time
Given the retained states, , final time , step lengths, time integration method, cycle type, and tolerance .
Construct the voxel hierarchy down to one voxel and its transfers by Algorithm 3.3, and form the generators using (19).
Initialize and .
for each prescribed step of length up to do
Form and from using (9).
Form , relaxation factors, and the bottom factorization, reusing them when is unchanged.
Initialize and .
while do
using Algorithm 3.2.
.
end while
Accept and advance .
end for
return the fine probability distribution at .
Algorithm 3.2 One multigrid cycle
Input level and right-hand side , and initialize .
if (one-voxel CME) then
return by the bottom direct solve.
end if
Apply forward relaxation to .
Form and restrict using Algorithm 3.4.
Recurse toward the CME to compute by (27) for the V- or W-cycle, or by residual minimization for the K-cycle.
Prolong and add using Algorithm 3.5.
Apply reverse relaxation to and return .
Algorithm 3.3 Construct restriction and prolongation for adjacent levels
Given fine and coarse state lists, aggregates , and volumes, initialize for every coarse index .
for each fine state with index do
for every aggregate and species.
Let be the index of in the coarse state list, with .
.
end for
for each fine index do
.
end for
return parent and weight.
Algorithm 3.4 Restrict a fine residual
1: Given fine residual $r$ and `parent`, initialize $b_c \leftarrow 0$.
2: **for** each fine index $i$ **do**
3: $(b_c)_{\mathrm{parent}[i]} \leftarrow (b_c)_{\mathrm{parent}[i]} + r_i$.
4: **end for**
5: **return** $b_c = Rr$.
Algorithm 3.5 Prolong and add a coarse correction
1: Given coarse correction $e_c$, fine iterate $x$, `parent`, and `weight`.
2: **for** each fine index $i$ **do**
3: $x_i \leftarrow x_i + \mathrm{weight}[i]\,(e_c)_{\mathrm{parent}[i]}$.
4: **end for**
5: **return** the updated fine iterate $x$.
Approximation Properties
We first state the Galerkin closure property verifying that the coarse reaction and diffusion rates in (21) and (22) reproduce . We then characterize the fine error omitted by the coarse projection under reversible diffusion, showing that averages the relative error over each coarse class and that the omitted variance is bounded by the internal aggregate Dirichlet energy with a constant independent of population. Finally, we state the resolvent bound used by the stopping rule. Complete proofs of Theorem 4.1, Lemma 4.2, Proposition 4.3, and Proposition 4.4 are given in Appendix A.
Coarse Generators
For distinct coarse states , the off-diagonal sum in (20) is nonnegative because the two fine classes are disjoint and . Moreover, (16) and imply , so is a Markov generator with absorbing boundary losses. Averaging the diffusive jumps of each molecule under the binomial marginal of (13) yields the coarse jump rate (21), and evaluating the factorial moments of (13) establishes the coarse reaction propensities.
Theorem 4.1. If contains complete population blocks and is uniform within each aggregate, then the reaction part of has propensity (22), including losses to omitted destination states.
Diffusion and the Coarse Approximation
We now construct the equilibrium weights and derive the graph energy introduced in (10). Assume that the voxel graph is connected and that every edge has positive diffusive jump rates satisfying . Because diffusion preserves each species total, every population block is a finite closed communicating class of . For one species at total population , the multinomial distribution
assigns positive weight to each arrangement and sums to one by the multinomial theorem. For a jump moving one molecule from voxel to voxel , the weights satisfy
equating the forward and reverse equilibrium fluxes across every edge and implying stationarity under . For several species, the product of their single-species distributions (29) gives the normalized diffusion equilibrium on each population block, which may be scaled by any positive block weight without requiring an equilibrium assumption for the reaction channels.
Letting and , detailed balance and stationarity read
so multiplying on the right by produces a symmetric positive semidefinite graph Laplacian [1, 6],
with nonpositive off-diagonal entries and zero row sums. Writing an error vector in terms of its relative entries as , pure diffusion takes the form
and differentiating yields the energy dissipation identity
matching the graph energy in (10). If , then and the mode decays as with decay rate .
Conditioning the global equilibrium weights on the coarse aggregate counts recovers the multinomial prolongation weights (13) and characterizes the projection error as a conditional variance.
Lemma 4.2. For reversible diffusion,
and the error omitted by satisfies
For the represented error , the relative entries equal the conditional average of over all fine states in coarse class , and (32) measures the variance lost in this averaging, as illustrated in Figure 3.

Figure 3. Diffusion state graph for one species with on a chain of three voxels of equal volume, with aggregates and . Each shaded row is one coarse state , and averages the relative error over the fine states in that row. Solid edges represent jumps inside an aggregate and contribute to , whereas dashed edges change the coarse state. The weights below the lowest row are its prolongation weights.
Diffusive jumps that preserve the coarse state move molecules only inside aggregates. Let denote the sum in (10) restricted to jumps inside aggregates. For each species and each aggregate containing at least two voxels, consider a single molecule confined to that aggregate, and let be the minimum of the smallest positive eigenvalues of these single-molecule negative diffusion generators across all species and multi-voxel aggregates.
Proposition 4.3. Under these assumptions,
Because is determined by single-molecule diffusion on each aggregate, the constant depends on the aggregates and jump rates but is independent of the molecular population. Relative errors that vary little across diffusive jumps inside aggregates are therefore approximated by the coarse space with accuracy independent of population size. A convergence estimate for the complete cycle would also require bounds for relaxation and recursive coarse solves. When the full reacting system satisfies detailed balance, exact coarse correction also minimizes an operator energy norm, as shown in Supplementary Section S2.2.
Accuracy of the Linear Solves
The stopping rule bounds the algebraic error in a completed linear solve through the computable fine residual, without requiring reversibility or an equilibrium assumption.
Proposition 4.4. If has nonnegative off-diagonal entries and nonpositive column sums, then for with ,
When , any marginal probability formed by summing a subset of entries of has algebraic error at most . Errors from earlier steps, time discretization, and FSP truncation are assessed separately.
Numerical Experiments
The experiments first examine how spatial levels, cycle choice, and relaxation affect convergence as the population cap and spatial grid are refined, comparing individual linear solves at a common tolerance through (33). We then apply the solver to transient distributions with two population peaks and to rare switching probabilities, assessing population truncation and time discretization separately.
Experimental Setup
We test single-species models on uniform Cartesian grids of total volume one with reflecting boundaries. Let be the count in voxel and the total population, whose marginal distribution is obtained by summing probabilities over all states with total .
We consider a linear immigration–degradation model with birth propensity and death propensity , together with the bistable Schlögl system [24], whose birth and death propensities in voxel are
For individual linear solves, we let and and initialize the iteration with , corresponding to one backward Euler step. The linear model uses and starts with one molecule in each of the first two voxels. The Schlögl tests use four voxels on a chain of length one, , and two molecules per voxel. Transient experiments specify their own initial states and step sizes.
The solver uses double precision and compressed sparse row (CSR) matrices on an Apple M1 Pro with 16 GB of memory. Unless stated otherwise, the stopping tolerance in (33) is . Point relaxation uses two forward and two reverse sweeps per level and block relaxation uses one sweep in each direction, except in direct comparisons where both use a single forward and reverse sweep. The ILU-GMRES baseline applies ILU(0) right preconditioning to the full matrix in GMRES(30) with the same stopping bound (33), and runs reaching the iteration limit are marked as unconverged. Reported timings come from single runs and include setup, which is reused across steps when is unchanged. Repeated-run implementation timings are reported in Supplementary Section S4.4.
Convergence and Refinement
We first examine the effect of retaining an intermediate spatial level on the four-voxel Schlögl problem at cap 80, where the fine level has 1,929,501 states, the two-voxel level has 3,403 states, and the bottom CME has 81 states. With identical point relaxation and initial guess, omitting the two-voxel level requires 188 iterations, whereas the hierarchy requires 97 V-cycles or 89 W-cycles (Figure 4, left).
Figure 4. Residual bound (33) for the Schlögl problem on four voxels at cap 80 (left) and the linear model on 1,024 voxels at cap 2 (right), with the common point relaxation and parameters specified in the setup. Direct CME correction omits intermediate spatial levels, which V and W retain. Table 1 gives the K-cycle results for the problem on the right.
On the linear problem with 1,024 voxels at cap 2 (11 levels and 525,825 fine states), the V-cycle fails to converge within 1,000 cycles, whereas the W- and K-cycles converge in 111 and 55 cycles (Figure 4, right, and Table 1). The K-cycle nearly halves the solve time relative to the W-cycle, while their shared setup cost reduces the saving in total time to about 17%.
| cycle | iterations | final bound | setup | solve | GiB |
| V | 1000 (limit) | 13.33 | 42.69 | 0.214 | |
| W | 111 | 13.36 | 6.92 | 0.228 | |
| K | 55 | 13.47 | 3.35 | 0.223 |
Table 1. Cycles for the linear problem on 1,024 voxels at cap 2, , and , using the same levels and point relaxation. V reaches the iteration limit, whereas W and K meet tolerance . Times are in seconds and peak memory is in GiB, with one run per cycle type.
To test population refinement, we increase from 2 to 8 on 16 voxels while retaining the five spatial levels. In Table 2, a 4,800-fold increase in the state count raises the W-cycle count only from 30 to 37, with K-cycle counts of 30, 33, 35, and 35, whereas direct CME correction rises from 214 to 501 iterations. These nearly flat multilevel counts are consistent with the population-independent constant in Proposition 4.3, although that approximation bound alone does not establish the full cycle convergence rate.
| cap | states | CME correction | W-cycle |
| 2 | 153 | 214 | 30 |
| 4 | 4,845 | 359 | 34 |
| 6 | 74,613 | 455 | 36 |
| 8 | 735,471 | 501 | 37 |
Table 2. Population refinement on 16 voxels for the linear model, , , with default point relaxation and tolerance . CME correction omits intermediate spatial levels.
For spatial refinement we fix and increase the voxel count in one, two, and three dimensions. This small cap permits grids up to 1,024 voxels (525,825 states) to isolate linear-solver scaling on the specified finite matrices, while FSP truncation accuracy is examined in the transient experiments below. Figure 5 compares the W- and K-cycles against ILU-GMRES. In one dimension, refining from 64 to 1,024 voxels raises the W-cycle count from 53 to 111 and the K-cycle count through 40, 44, 48, 51, and 55, whereas ILU-GMRES converges within 1,000 iterations only on 64 voxels (and remains at bound 0.207 after 5,000 iterations on 1,024 voxels).
Figure 5. Spatial refinement for the linear model at cap 2, with W and K reporting cycles and ILU-GMRES reporting iterations. All methods use tolerance , and the cycles use two point Gauss–Seidel sweeps in each direction. Open markers indicate runs that reach the iteration limit. The counts compare convergence, with different costs per iteration for the three methods.
The largest two-dimensional grid (32 × 32) requires 46 W-cycles, 40 K-cycles, or 394 ILU-GMRES iterations, compared with 27, 28, and 57 on the largest three-dimensional grid (8 × 8 × 8). The K-cycle is therefore most advantageous on the deepest hierarchy in one dimension and does not reduce the cycle count on every grid.
Smoothing and Computational Cost
Table 3 compares point and block Gauss–Seidel relaxation using one forward and reverse sweep per level. Block updates reduce both the W-cycle count and total elapsed time across all tested problems. For the four-voxel Schlögl benchmark at cap 40, switching from point to block smoothing reduces the cycle count from 110 to 40 and cuts total time from 0.706 to 0.362 seconds.
| model | voxels | cap | states | cycles | total time (s) |
| Schlögl | 4 | 40 | 135,751 | 110 / 40 | 0.706 / 0.362 |
| Schlögl | 4 | 60 | 635,376 | 154 / 56 | 4.884 / 2.343 |
| linear | 16 | 8 | 735,471 | 50 / 28 | 2.888 / 2.265 |
| linear | 64 | 4 | 814,385 | 67 / 48 | 4.590 / 4.390 |
Table 3. Point and block relaxation in W-cycles for one linear solve, using one forward and one reverse sweep per level. Each pair of entries lists the point result first and the block result second. Times include setup and solve, in seconds from individual runs.
Block relaxation alone does not replace coarse correction. After 300 forward and reverse block sweeps without coarse correction on the cap-40 Schlögl problem, the residual bound remains above 0.248. With the 4 2 1 hierarchy, W- and K-cycles require 40 and 41 cycles at cap 40, and 56 and 57 cycles at cap 60. On these shallow hierarchies, strengthening the smoother from point to block relaxation has a much larger effect than changing the W-cycle to a K-cycle.
To compare multigrid with sparse direct factorization, we test KLU [7] with approximate minimum degree (AMD) ordering [3]. On the 1,024-voxel linear benchmark, the point W-cycle takes 20.3 seconds including setup and uses 0.23 GiB of memory, whereas KLU takes 31.4 seconds and 1.16 GiB (Table 4). Once factored, however, KLU solves each subsequent right-hand side in 0.19 seconds compared with 6.92 seconds for the W-cycle, recovering its larger setup cost after about three solves when the factors fit in memory.
Cost at tolerance , with times in seconds and peak memory in GiB. The linear problem has 1,024 voxels and , while the Schlögl transients on four voxels use , , and 21 solves with reused setup. All use . Point and block use their default numbers of sweeps, and a dash denotes direct solution.
| method | states | cycles | setup | solve | GiB | |
| Linear model | ||||||
| KLU | 2 | 525,825 | — | 31.17 | 0.19 | 1.16 |
| point W | 2 | 525,825 | 111 | 13.36 | 6.92 | 0.23 |
| Schlögl transient | ||||||
| point W | 96 | 3,921,225 | 1481 | 1.06 | 435.57 | 1.02 |
| block W | 96 | 3,921,225 | 1072 | 1.56 | 261.47 | 1.50 |
| point W | 112 | 7,160,245 | 1481 | 1.74 | 816.72 | 1.71 |
Table 4.
On the nonlinear Schlögl system on four voxels, KLU factors the matrix at cap 20 but exceeds the 2 GiB SuiteSparse allocation limit at cap 32 and higher caps, where symbolic analysis predicts nonzeros per triangular factor at cap 32 and at cap 80. Multigrid completes the transient integrations at caps 96 and 112 within 1.71 GiB while reusing its setup across all 21 steps.
Transient Distributions
We next integrate the Schlögl distribution from to on four voxels with using Crank–Nicolson with two initial backward Euler half-steps, without clipping negative entries or renormalizing the solution vector. Figure 6 shows the evolution of the population marginal, the mass above , and the -cycle counts per solve.
Figure 6. Schlögl evolution on four voxels from , , , and algebraic tolerance . Panels (a,b) use cap 96 and block W. Panel (c) compares population caps at , and panel (d) compares the number of point and block W-cycles per solve at cap 96.
At , the distribution exhibits two population modes at and . Increasing the cap from 80 to 96 changes by , and increasing it from 96 to 112 (7,160,245 fine states and 113 CME states) changes by and the population marginal by in (Table 5). At cap 96, point and block relaxation produce final marginals agreeing to in , while block relaxation reduces runtime from 437 to 263 seconds and increases peak memory from 1.02 to 1.50 GiB.
Population refinement for the Schlögl transient on four voxels at , , with and tolerance . The reported mass is subject to errors from time discretization and linear solves.
| relaxation | states | retained mass | ||
| block | 80 | 1,929,501 | 0.9932912374 | 0.4491884933 |
| block | 96 | 3,921,225 | 0.9999815048 | 0.4556061510 |
| point | 112 | 7,160,245 | 0.9999999950 | 0.4556239278 |
Table 5.
At cap 112, halving the step size through , 2.5, and 1.25 gives , 0.4557196041, and 0.4557434892 in 818, 1,716, and 2,438 seconds, respectively. The successive differences and decrease by a factor of four, consistent with second-order temporal convergence, and Supplementary § 4.3.1 provides an independent uniformization check on two voxels.
Rare Population Switching
To test direct resolution of rare events [19], we initialize the four-voxel Schlögl chain in the empty state with and , and integrate to . The resulting population marginal has a dominant mode at and a faint secondary peak at separated by a minimum near (Figure 7). At cap 72 and with tolerance (1,282,975 states), the multigrid FSP solver gives and . A calculation at cap 56, , and tolerance (487,635 states) takes 37.4 seconds (66.1 seconds without the intermediate two-voxel level, see Supplementary § 4.4.4) and matches to within 0.137% (refinements in Supplementary Table S1).
Figure 7. Rare switching at . Panel (a) compares FSP at cap 72, , with SSA, omitting bins with zero observed endpoints from the logarithmic axis. The first million paths belong to the sample of 60 million paths. Panels (b,c) show the secondary peak and the observed and expected counts for individual integer populations. Supplementary Table S1 gives the FSP refinements.
In comparison, independent SSA trajectories [11] produce three endpoints with and none at , while trajectories (673.5 seconds) produce 96 and four endpoints, respectively. Using the relative standard error for trajectories, the refined FSP probabilities predict 9.7% relative standard error for and 50% at . Reaching 10% relative standard error at with independent SSA paths would require about trajectories, whereas specialized rare-event sampling methods can reduce variance when targeted to a reaction coordinate [2].
Concluding Remarks
We have developed a multigrid method for the finite state projection of the RDME by combining fine-grid relaxation with coarse corrections on aggregated voxel grids. Summing molecular counts over voxel aggregates and distributing coarse corrections with multinomial weights preserves the RDME generator structure and absorbing losses on every level down to a single-voxel CME. For reversible diffusion, the intergrid transfers average the error relative to equilibrium across each coarse count class, and the omitted variance is bounded by the internal aggregate graph energy with a constant independent of population.
The numerical experiments demonstrate that retaining intermediate spatial levels reduces iteration counts and runtime relative to direct CME correction, that W- and K-cycles prevent convergence degradation on deep one-dimensional hierarchies, and that block Gauss–Seidel relaxation accelerates convergence on strongly coupled nonlinear populations, reaching 7.16 million states and resolving switching probabilities of order . Establishing uniform convergence bounds for the full reacting cycle and combining voxel aggregation with low-rank state compression remain natural directions for future work.
Appendix A. Proofs of Approximation Properties
This appendix gives the proofs of Theorem 4.1, Lemma 4.2, Proposition 4.3, and Proposition 4.4 stated in § 1.4.
Proof of Theorem 4.1. Let denote expectation under the prolongation weights (13) conditioned on a coarse state . Under (13), the fine count in voxel has a binomial marginal distribution with trials and success probability . For , the identity gives the factorial moment
which also holds when since both sides vanish. Because the weights [13] factor independently across species and , summing [5] over yields
Every occurrence of reaction at any fine voxel produces the same coarse state change in row of . Because is a union of complete population blocks, a fine destination state belongs to if and only if its coarse destination belongs to . An omitted destination state therefore leaves the averaged loss on the diagonal of without a matching off-diagonal entry. □
Proof of Lemma 4.2. Consider a coarse state at index with species totals . Let be the positive weight assigned to population block and . Regrouping the equilibrium weights (29) by aggregate and comparing with [13] gives, for every fine state with ,
The positive factor preceding depends only on the coarse state . Because retains complete population blocks, the multinomial theorem implies . Summing the factorization of over therefore identifies the prefactor as , and dividing by establishes (31) with canceling from the ratio.
For each fine index , let be its unique coarse index with . By [14] and (31), the prolonged restricted error has entries
Substituting and partitioning the sum over fine states by their coarse index gives
which proves (32). □
Proof of Proposition 4.3. Fix a coarse state at index with fine equivalence class and conditional weights . If , both its conditional variance and internal Dirichlet energy vanish. Otherwise, temporarily label the molecules of each species in each aggregate and let each labelled molecule diffuse independently on the connected subgraph with reversible single-molecule generator and stationary distribution (). On the product space of labelled placements , the joint stationary measure and generator are
Because the eigenvalues of are sums of the nonnegative eigenvalues of , the smallest positive eigenvalue of is at least . The spectral expansion on therefore yields the Poincaré inequality
Evaluating this inequality on functions that depend only on the unlabelled voxel counts , sums over the permutations in each count state to recover the multinomial weight and the count-space jump rates . Consequently,
Multiplying by and summing over all coarse classes yields by (32).
Proof of Proposition 4.4. For , the shifted matrix has nonnegative entries, so is entrywise nonnegative for all . Since , differentiating shows that the column sums of do not exceed one, giving . For , the Laplace integral for the resolvent gives
Applying this operator norm bound to establishes (33).
Code Availability
The solver and reproduction scripts are available at https://github.com/AdityaDendukuri/markovkit/tree/main/rdme.
SUPPLEMENT TO A MULTIGRID FINITE STATE PROJECTION ALGORITHM FOR THE SOLUTION OF THE REACTION-DIFFUSION MASTER EQUATION
Aditya Dendukuri; Linda Petzold
Section S1 walks through an explicit algebraic example of the state space and transfer operators on two voxels, followed by a coarse correction step. Section S2 derives the orthogonalized K-cycle coefficients, the two-grid energy optimality under detailed balance, and the operation count per cycle. Section S3 presents independent uniformization checks and the adaptive population enlargement algorithm, together with the discretization refinement study for rare switching. Section S4 examines matrix storage, transfer sparsity patterns, and exact reduction under reflection symmetry, while Section S5 illustrates spatial front propagation in a bistable Schlögl chain using exact trajectory simulations. We retain all notation and solver conventions of the main paper, and any section or equation number without an S prefix refers to the main paper.
supplement.pdf
A Worked Example
A linear immigration and degradation network illustrates how the generator and transfer operators are constructed on a domain of two voxels, together with the resulting Galerkin coarse system. As in the main paper, columns of the generator correspond to source states.
State Space and Generator
Consider a single chemical species S in a compartment of unit volume (), subject to immigration with propensity 1 and degradation with propensity . In this single-voxel CME, the states are the integer copy numbers , and the probability vector has one component for each count. An immigration event transfers probability flux from component to component .
Partitioning the unit domain into two voxels of equal volume yields spatial configurations with joint probabilities . In each voxel , immigration occurs at rate and degradation occurs at rate . Let denote the diffusive jump rate per molecule between the two voxels. An immigration event in voxel 1 transitions state to at rate , whereas a diffusive jump transitions to at rate .
Truncating the state space by total population with cap retains the six configurations
Ordering the probability vector according to (S1.1) groups states by total population . The configuration is excluded because the FSP cap bounds the total copy number rather than each voxel count separately. Any immigration event occurring in the block transitions to a state with outside the retained set, so its outgoing rate 1 remains on the diagonal as an absorbing loss. Assembling all reaction and diffusion transitions yields the FSP generator
The first three columns correspond to states with and have column sums equal to zero, whereas the last three columns correspond to and have column sums equal to due to the absorbed immigration flux. Increasing the cap from to appends the four states , enlarging the probability vector from six to ten components while keeping two voxel coordinates per state.
Restriction and Prolongation
Aggregating the two voxels into a single coarse compartment of volume gives the coarse count . The restriction operator sums entries over fine configurations with the same total , while the prolongation operator distributes each molecule independently into voxel 1 or voxel 2 with equal probability . In the state ordering (S1.1), these operators take the block-diagonal form
In the solver implementation, the nonzeros of and are stored in the two length-6 arrays
using zero-based coarse indices. For an example fine probability vector, restriction sums within each population block according to
| fine states | fine probabilities | ||
| 0 | (0, 0) | 0.10 | 0.10 |
| 1 | (1, 0), (0, 1) | 0.10, 0.10 | 0.20 |
| 2 | (2, 0), (1, 1), (0, 2) | 0.14, 0.35, 0.21 | 0.70 |
Table S1.4.
Applying the projection to this probability vector gives
The projected vector preserves the coarse marginal while replacing the asymmetric entries on the block by the binomial values . Although ensures that restricting a prolonged vector recovers the coarse vector, has rank three and cannot recover the fine components in the null space of .
This two-voxel system can itself serve as an intermediate level in a deeper hierarchy. Starting from a chain of four voxels at cap (15 states), pairing voxels and maps a fine state such as to the two-voxel state and then to the single-voxel CME state 2, reducing the state-space dimension through while retaining all populations up to cap two on every level.
The Coarse Generator
Forming the Galerkin projection of (S1.2) with the transfer matrices (S1.3) produces the coarse generator
All diffusive parameter terms cancel identically in because diffusive jumps remain within the single aggregate . The coarse immigration rates sum to , the coarse degradation rates sum to , and the third column retains its column sum of from the absorbed immigration channel at . Thus is the exact FSP generator of the single-voxel CME at cap two.
When a two-voxel grid arises by coarsening a four-voxel chain of uniform spacing and fine jump rate , only the boundary voxel inside each two-voxel aggregate is adjacent to the interface between the two aggregates. Because a molecule in either aggregate occupies that boundary voxel with probability , the Galerkin coarse jump rate (21) between the two aggregates is . By contrast, naive finite-difference rediscretization at coarse mesh spacing with diffusivity would assign jump rate , differing by a factor of two from the Galerkin rate .
A Coarse Correction
To trace a single coarse-grid correction step, consider backward Euler with step size () starting from the empty state . Initializing the solve with for gives the fine residual and its restriction
Solving the shifted coarse equation yields
Prolonging by and adding the correction to produces the updated fine iterate
Direct multiplication verifies that for every , with retained probability mass . Because the initial state and linear reaction propensities in this spatially symmetric model preserve the binomial distribution across the two voxels, the exact solution lies entirely in the range of and is recovered in a single coarse correction without relaxation.
Nonlinear Reactions and Coarse Approximation
When nonlinear reactions are present, the fine solution no longer lies in the range of . Suppose we add the bimolecular birth reaction with rate constant in each voxel of volume . Its combined propensity across the two voxels is
which evaluates to , , and on the three states , , and of the block. Averaging these three values with the binomial prolongation weights gives the coarse propensity at , in agreement with Theorem 4.1. The true outgoing flux from the block, however, depends on how much probability resides in versus and , so the coarse counts do not evolve autonomously and the solver must iterate on the fine system.
On the block, an error subvector proportional to the binomial weights lies in the range of and is reproduced exactly by , whereas an oscillatory error subvector lies in the null space of and is omitted by . Proposition 4.3 bounds this omitted component in terms of the Dirichlet energy of diffusive jumps between the two voxels, while relaxation sweeps on damp directly on the fine grid.
Multigrid Analysis
Among the analytical results below, only the orthogonality argument in Section S2.2 assumes detailed balance for the full reacting FSP generator.
K-Cycle Coefficients
The K-cycle chooses coefficients for recursive corrections by minimizing the coarse Euclidean residual norm. Let be the restricted residual from § 1.3.6 and let . A zero right-hand side returns zero, and a direction with zero image under leaves the correction unchanged, so we evaluate the following weights only when their denominators are nonzero. The first recursive direction and the residual after optimal scaling are
When , the correction is accepted. Otherwise, we compute a second recursive direction from and subtract its component along the first so that their images under are orthogonal,
The orthogonality relations and imply that these coefficients minimize over the span of the two directions. At the bottom CME level, the direct solve replaces this minimization.
Equations (S2.1) and (S2.2) perform at most two steps of preconditioned generalized conjugate residual minimization [20], whose dependence on makes the cycle nonlinear. We therefore apply the K-cycle directly as an iterative solver and use the linear W-cycle when right-preconditioning GMRES [22].
Coarse Correction under Detailed Balance
The coarse representation and the Galerkin coarse correction both lie in the range of , but their coefficients are determined differently. Whereas uses restriction alone, the coarse correction solves the Galerkin system for the restricted residual. For with , an exact coarse solve maps an error to , where
The identities , , and show that an exact coarse correction removes any error component in the range of and leaves zero restricted residual. Under detailed balance, the standard Galerkin argument [28] shows that this correction minimizes a weighted operator energy norm.
Let be positive weights on the retained fine states, with and , and retain . For example, linear immigration at rate and degradation at rate () under reversible diffusion admit independent Poisson weights with means [4], whose conditional distribution on the aggregate counts equals the prolongation weights .
Assume that holds for the complete retained generator and that whenever . The weighted operator is then symmetric and satisfies
Since the absorbing loss rate from state to omitted states is , the quadratic form of in terms of the relative error is
The shift, transitions between retained states, and absorbing losses each contribute nonnegative terms, so is an energy norm on . If retains only diffusive jumps inside aggregates, Proposition 4.3 gives
By (S2.3), the corrected error is orthogonal in the -norm to the range of , giving
and hence
An exact coarse solve therefore selects the prolonged correction that minimizes the remaining error in the -norm.
The point Gauss–Seidel smoother of § 1.3.5 also reduces this norm. For the error before updating component and afterward, gives
Equality over a full sweep requires every update to vanish, implying and . Compactness of the unit energy sphere then implies strict two-grid contraction on each finite system, with a factor that may depend on system size.
In a multilevel cycle, let and denote the error propagators of forward and reverse relaxation on level , and let denote the error propagator of the complete cycle. The direct bottom solve gives , while the V- and W-cycles satisfy
with for V and for W. Because the K-cycle weights depend on the residual, K has no single linear error propagator, and none of these identities alone establishes a uniform convergence rate.
The nonlinear Schlögl experiments do not assume detailed balance for the complete generator, so this -norm argument does not apply to them. Their diffusion part still has the graph energy in (10), and the transfer operators, coarse rates, and residual bound of Proposition 4.4 hold without reversibility of the full system.
Matrix Size and Work per Cycle
The work estimate in § 1.3.7 follows from the number of nonzeros on each level and the number of recursive visits. Consider a birth–death system for one species on voxels at cap , and let be the edge set of the voxel graph. Each edge permits diffusion in both directions, so when all permitted event rates are positive the shifted matrix has
For each voxel, states contain at least one molecule there and the same number lie below the cap and permit a birth. On a -dimensional Cartesian grid with , this yields
For fixed , the state count is asymptotic to , so coarsening by voxels reduces the leading term by on level . With at most visits per W-cycle, the total work is bounded by a geometric sum of ratio , which is independently of the number of levels when and when . The V- and K-cycles have the same asymptotic work bound per cycle, excluding setup and the number of cycles required for convergence.
Numerical Validation
These checks assess numerical accuracy separately from the cost comparisons in Section S4.
Uniformization
On smaller state spaces we check the time integration independently by uniformization [25], which evaluates the matrix exponential as a Poisson-weighted series of powers of a shifted transition matrix without solving linear systems. For the larger four-voxel systems, we instead use the population and time refinements in § 1.5.4.
For the Schlögl transient on two voxels at cap 40, uniformization with subintervals corresponding to Poisson means 4 and 8 produces reference probability vectors agreeing to in . Relative to this reference at , the Crank–Nicolson integrator with backward Euler startup has errors , , , and at , 5, 2.5, and 1.25, respectively.
Adaptive Population Selection
The adaptive FSP algorithm selects the population cap from a cumulative error budget while retaining complete population blocks on every level. At each trial step, we apply backward Euler to the current FSP system and bound the algebraic solve error using Proposition 4.4. Because the exact backward Euler resolvent is contractive in the norm, the sum of residual bounds over accepted steps bounds the accumulated algebraic error of the linear solves.
A trial step is accepted when its computed missing mass plus twice this accumulated sum of solve bounds (including the current trial bound) does not exceed the total error budget multiplied by the elapsed time fraction . One copy of the accumulated solve bound accounts for the difference between the computed missing mass and the exact FSP truncation loss, and the second copy bounds the algebraic error in the returned vector . Rejected trial steps do not contribute to the accumulated sum.
Whenever a trial step violates this acceptance bound, the driver increases the population cap from to across all levels of the spatial hierarchy and repeats the step from the saved distribution , padding the newly added population blocks with zeros without renormalizing previously absorbed mass. All existing diagonal blocks and their ILU(0) factors are retained without recomputation, along with the existing transfer entries. This procedure guarantees that the accepted discrete trajectory satisfies at every step, while temporal discretization error relative to the continuous-time RDME is controlled through .
Refinement of the Rare-Switching Calculation
Table S1 reports the cap and step-size refinements for the rare-switching problem of Section 5.5 on four voxels at . Every linear solve converges to the prescribed tolerance ( at cap 56 and at caps 64 and 72), and all final probability entries are nonnegative without clipping or renormalization. These sequential timings include solver setup and file output on the benchmark hardware of Section 5 using the unreduced state representation, and are separate from the paired implementation comparisons in Section S4.4.
| cap | states | time (s) | |||
| 56 | 10 | 487,635 | 37.4 | ||
| 64 | 5 | 814,385 | 134.4 | ||
| 64 | 2.5 | 814,385 | 231.3 | ||
| 72 | 5 | 1,282,975 | 209.3 |
Table S1. Discretization refinement for the rare-switching RDME on four voxels at . All runs use the W-cycle with one forward and one reverse ILU(0) block sweep per level, with solve tolerance at cap 56 and at caps 64 and 72.
Implementation and Computational Cost
Matrix Storage and Factor Reuse
To minimize memory overhead and setup time, the solver exploits the bipartite graph structure of Cartesian diffusion blocks during ILU(0) factorization. On a bipartite voxel graph (such as any Cartesian mesh under a red–black checkerboard coloring), every diffusive jump transfers a molecule between a red voxel and a black voxel, changing the parity of the total molecule count on the red voxels by . Consequently, the diffusion transition graph within each population block is itself bipartite and contains no odd cycles, and in particular no triangles (3-cycles). During an ILU(0) factorization of a diagonal block , an off-diagonal entry is modified by elimination of a prior pivot only if , , and are all nonzero, which would form a triangle in the diffusion graph. Because no such triangles exist, all off-diagonal entries of the ILU(0) factors coincide identically with the off-diagonal entries of , and only the modified diagonal pivots need to be computed and stored. Forward and backward triangular solves in (26) therefore read the off-diagonal entries directly from , avoiding duplicate sparse matrix storage while producing the exact same ILU(0) update in floating-point arithmetic. We also fuse the block residual evaluation with the forward sweep and reuse workspace buffers across time steps.
Structure of the Transfer Operators
To visualize the algebraic structure of the transfer operators in the Schlögl benchmark on four voxels at cap 40 (Table 3), we export the arrays parent and weight from the hierarchy (135,751 861 41 states) and plot all nonzero locations in Supplementary Figure S1. In the solver’s native ordering, states are sorted first by total population and then lexicographically by voxel counts. Because and conserve total population, both matrices are block diagonal across the 41 population blocks, and the sparsity pattern of is the exact transpose of that of .
Figure S1. Sparsity patterns of the restriction and prolongation operators from the Schlögl benchmark on four voxels at cap 40. Panels (a,b) display the transfers (135,751 nonzeros each), and panels (c,d) display the transfers (861 nonzeros each) in the solver’s native ordering. Every nonzero entry is plotted as a black point using zero-based indices. The upward curvature reflects the cubic growth of the population block sizes on four voxels.
Supplementary Figure S2 zooms into the single population block of the transfer operators, which maps 35 fine states on four voxels to 5 coarse states on two voxels. In the native lexicographic ordering (panels a and b), fine states belonging to different coarse states (, ) are interleaved. Permuting the 35 fine states so that arrangements sharing each of the five coarse states (4, 0), (3, 1), (2, 2), (1, 3), and (0, 4) are contiguous (panels c and d) reveals five disjoint rectangular blocks of sizes 5, 8, 9, 8, 5 as in (15). Within each block, restriction sums the fine entries with a row of ones, and prolongation distributes the coarse entry with the corresponding column of multinomial weights.
Figure S2. Sparsity pattern of the population block (35 fine states and 5 coarse states) of the transfer operators. Panels (a,b) use the solver’s native lexicographic ordering, whereas panels (c,d) group fine states by their coarse counts to display the five disjoint rectangular blocks of (15). Restriction has dimension and prolongation has dimension , with 35 nonzeros in each panel.
Exact Reduction by Reflection Symmetry
When the model and initial distribution are invariant under spatial reflection, the FSP state space can be compressed exactly by grouping configurations that are related by reflection. On a chain of voxels of equal volume with spatially uniform rates, reversing the voxel index map commutes with the FSP generator (and similarly along each coordinate axis on a -dimensional Cartesian grid). Consequently, any configuration and its reflection carry identical probability at all times . Storing the combined probability as a single unknown for each asymmetric pair and storing symmetric configurations () once halves the asymptotic dimension of the system, while the full probability vector is recovered exactly by dividing each paired entry by two.
Summing the outgoing transition rates from a representative source state into each destination group gives the exact reduced generator with the same absorbing boundary losses. Because uniform voxel aggregation commutes with spatial reflection, restriction still sums reduced entries and prolongation weights each fine group by its summed multinomial weight. Unlike the bipartite unreduced graph in Section S4.1, identifying reflected states can introduce triangles into the reduced diffusion graph, so the reduced solver uses a general sparse ILU(0) factorization on each diagonal population block while keeping the bottom CME on one voxel unchanged.
Computational Cost
We now evaluate the memory and runtime reductions obtained from the ILU(0) storage of Section S4.1 and the reflection reduction of § 4.4.3 while holding the FSP system and multigrid parameters fixed. All runs use the W-cycle with one forward and one reverse block Gauss–Seidel sweep per level. Each paired comparison executes two sequential repetitions in alternating order on the same machine, and all reported elapsed times include setup and time integration together with exporting the complete unreduced probability vector.
On the rare-switching integration on four voxels at cap 56 without reflection reduction, eliminating duplicate off-diagonal ILU(0) storage and fusing the sweep residual loop reduces mean elapsed time from 36.69 to 35.84 seconds and lowers peak resident memory by 35%, from 0.195 to 0.127 GiB, while the final probability vectors agree to in the norm.
Table S2 compares the baseline unreduced solver with the reduced solver under reflection symmetry on both the rare-switching calculation at cap 56 and an adaptive FSP Schlögl integration. The adaptive benchmark integrates the Schlögl model on four voxels from initial state to using backward Euler with , cumulative FSP error budget , and linear solve tolerance under the acceptance rule of Section S3.2. Both implementations dynamically expand the population cap from to through identical step rejections and execute 666 total W-cycles.
| Problem | Stored unknowns baseline | Stored unknowns reduced | Time (s) baseline | Time (s) reduced | Memory (GiB) baseline | Memory (GiB) reduced |
| Rare switching | 487,635 | 244,035 | 36.71 | 18.37 | 0.199 | 0.084 |
| Adaptive Schlögl | 2,123,555 | 1,062,229 | 60.03 | 30.50 | 0.903 | 0.486 |
Table S2. Comparison with exact reflection reduction on identical FSP problems on four voxels. Stored unknowns report the dimension on the finest grid, and elapsed time and peak resident memory are means of two alternating runs.
Halving the number of stored unknowns through reflection symmetry reduces mean elapsed time by factors of 2.00 and 1.97 (and CPU time from 36.45 to 17.92 seconds and from 59.55 to 29.94 seconds), while cutting peak memory by about half.2 The reconstructed fine probability vectors agree with the unreduced solutions to and in the norm, with all entries nonnegative.
Within the reduced solver on the rare-switching problem, omitting the intermediate level of two voxels increases the total cycle count from 1,215 (4 → 2 → 1) to 2,179 (4 → 1) and raises elapsed time from 18.37 to 32.18 seconds (a factor of 1.75), while the final probability vectors agree to in . Thus spatial coarsening and reflection reduction provide separate speedups whenever the problem is invariant under reflection.
Spatial Front Propagation
Because the FSP benchmarks on four voxels summarize spatial distributions primarily through the global population marginal , we include a separate trajectory simulation on a chain of 64 voxels to illustrate spatially inhomogeneous wave propagation in the bistable Schlögl model. This example is computed by Gillespie’s exact SSA [11] and illustrates the spatial RDME dynamics rather than the FSP linear solver.
Consider a chain of 64 reflecting voxels of volume and unit spacing, with diffusive jump rate 1 per molecule to each adjacent voxel. The local Schlögl reaction constants are chosen as , corresponding to a deterministic reaction drift for concentration with stable equilibria at () and () separated by an unstable barrier at (). We initialize the chain with a step interface placing 200 molecules in each of voxels 1, …, 16 and 40 molecules in each of voxels 17, …, 64, and simulate 256 independent SSA trajectories to , recording voxel counts every 2 time units.
Figure S3 plots the empirical probability that a voxel has concentration at least 5 as the stochastic front advances from voxel 16. At , we also extract the marginal count distributions at four representative voxel locations A–D across the 256 trajectories. Well behind the front (voxel A) and well ahead of the front (voxel D), the local count distributions are unimodal around 200 and 40 molecules, respectively. Inside the transition zone (voxels B and C, where equals 0.625 and 0.371), the local voxel marginals broaden across intermediate counts due to diffusive mixing and interface fluctuations, rather than splitting into two sharply separated peaks within a single voxel.
Figure S3. Propagation of a stochastic Schlögl front across a chain of 64 reflecting voxels estimated from 256 independent Gillespie SSA trajectories. The central space–time map shows the empirical probability . Surrounding histograms A–D show the normalized count distributions in individual voxels at (bin width 5 molecules) behind the front (A), inside the interface region (B and C), and ahead of the front (D).
Code Availability. The solver and reproduction scripts are available at https://github.com/AdityaDendukuri/markovkit/tree/main/rdme.
References
References
- [1]D. Aldous and J. A. Fill, Reversible Markov Chains and Random Walks on Graphs, unfinished monograph, 2002, recompiled 2014, https://www.stat.berkeley.edu/~aldous/RWG/book.html.
- [2]R. J. Allen, P. B. Warren, and P. R. ten Wolde, Sampling rare switching events in biochemical networks, Physical Review Letters, 94 (2005), 018104.pubmed.ncbi.nlm.nih.gov/15698138
- [3]P. R. Amestoy, T. A. Davis, and I. S. Duff, An approximate minimum degree ordering algorithm, SIAM Journal on Matrix Analysis and Applications, 17 (1996), pp. 886–905.
- [4]D. F. Anderson, G. Craciun, and T. G. Kurtz, Product-form stationary distributions for deficiency zero chemical reaction networks, Bulletin of Mathematical Biology, 72 (2010), pp. 1947–1970.
- [5]A. Brandt, Multi-level adaptive solutions to boundary-value problems, Mathematics of Computation, 31 (1977), pp. 333–390.
- [6]F. R. K. Chung, Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, vol. 92, American Mathematical Society, Providence, RI, 1997.
- [7]T. A. Davis and E. Palamadai Natarajan, Algorithm 907: KLU, a direct sparse solver for circuit simulation problems, ACM Transactions on Mathematical Software, 37 (2010), pp. 36:1–36:17.
- [8]H. De Sterck, T. A. Manteuffel, S. F. McCormick, K. Miller, J. Ruge, and G. Sanders, Algebraic multigrid for Markov chains, SIAM Journal on Scientific Computing, 32 (2010), pp. 544–562.
- [9]P. Deuflhard, W. Huisinga, T. Jahnke, and M. Wulkow, Adaptive discrete Galerkin methods applied to the chemical master equation, SIAM Journal on Scientific Computing, 30 (2008), pp. 2990–3011.
- [10]S. Engblom, L. Ferm, A. Hellander, and P. Lötstedt, Simulation of stochastic reaction-diffusion processes on unstructured meshes, SIAM Journal on Scientific Computing, 31 (2009), pp. 1774–1797.
- [11]D. T. Gillespie, Exact stochastic simulation of coupled chemical reactions, The Journal of Physical Chemistry, 81 (1977), pp. 2340–2361.DOI
- [12]D. T. Gillespie, A rigorous derivation of the chemical master equation, Physica A: Statistical Mechanics and its Applications, 188 (1992), pp. 404–425.DOI
- [13]M. Hegland, Approximating the solution of the chemical master equation by aggregation, ANZIAM Journal, 50 (2008), pp. C371–C384.
- [14]M. Hellander, A. Hellander, and P. Lötstedt, Sparse grids and hybrid methods for the chemical master equation, BIT Numerical Mathematics, 48 (2008), pp. 265–283.DOI
- [15]S. Hellander, A. Hellander, and L. Petzold, Reaction-diffusion master equation in the microscopic limit, Physical Review E, 85 (2012), 042901.pubmed.ncbi.nlm.nih.gov/22680526
- [16]S. A. Isaacson, The reaction-diffusion master equation as an asymptotic approximation of diffusion to a small target, SIAM Journal on Applied Mathematics, 70 (2009), pp. 77–111.DOI
- [17]V. Kazeev, M. Khammash, M. Nip, and C. Schwab, Direct solution of the chemical master equation using quantized tensor trains, PLoS Computational Biology, 10 (2014), e1003359.DOI
- [18]J. G. Kemeny and J. L. Snell, Finite Markov Chains, Springer-Verlag, New York, 1976.
- [19]B. Munsky and M. Khammash, The finite state projection algorithm for the solution of the chemical master equation, The Journal of Chemical Physics, 124 (2006), 044104.pubmed.ncbi.nlm.nih.gov/16460146
- [20]Y. Notay and P. S. Vassilevski, Recursive Krylov-based multigrid cycles, Numerical Linear Algebra with Applications, 15 (2008), pp. 473–487.DOI
- [21]Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, 2003.DOI
- [22]Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, 7 (1986), pp. 856–869.DOI
- [23]R. I. Saye, Cascading smoothers for multigrid, preprint, arXiv:2606.12577, 2026, https://arxiv.org/abs/2606.12577.
- [24]F. Schlögl, Chemical reaction models for non-equilibrium phase transitions, Zeitschrift für Physik, 253 (1972), pp. 147–161.
- [25]R. B. Sidje and W. J. Stewart, A numerical study of large sparse matrix exponentials arising in Markov chains, Computational Statistics & Data Analysis, 29 (1999), pp. 345–368.DOI
- [26]E. Treister and I. Yavneh, On-the-fly adaptive smoothed aggregation multigrid for Markov chains, SIAM Journal on Scientific Computing, 33 (2011), pp. 2927–2949.DOI
- [27]U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid, Academic Press, London, 2001.
- [28]J. Xu, Iterative methods by space decomposition and subspace correction, SIAM Review, 34 (1992), pp. 581–613.DOI






