betaFeedback

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 10−710^{-7}.

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 p˙=Ap\dot{p} = A p.

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 (σI−A)x=b(\sigma I-A)x=b at every step. Although the generator AA 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 10−710^{-7} 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 ω>0\omega> 0, the RDME reduces to the chemical master equation (CME). Consider NsN_{\mathrm{s}} chemical species S1,…,SNsS_1,\ldots,S_{N_{\mathrm{s}}} in a well-mixed volume ω>0\omega> 0. A state records their molecular counts,

X=(X1,…,XNs)∈N0Ns.X=(X_1,\ldots,X_{N_{\mathrm{s}}})\in\mathbb{N}_0^{N_{\mathrm{s}}}.

Let p(X,t)p(X,t) be the probability of state XX at time tt and collect these probabilities into the vector p(t)\boldsymbol{p}(t). A state XX has NsN_{\mathrm{s}} integer coordinates, whereas the probability vector p(t)\boldsymbol{p}(t) 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 p(t)\boldsymbol{p}(t).

In reaction channel rr, let αr,s\alpha_{r,s} and βr,s\beta_{r,s} denote the numbers of molecules of species ss consumed and produced, respectively, and let cr≥0c_r\geq0 be the rate constant. Writing αr=(αr,s)\boldsymbol{\alpha}_r=(\alpha_{r,s}) and βr=(βr,s)\boldsymbol{\beta}_r=(\beta_{r,s}), the reaction channel and its mass-action propensity are

∑sαr,sSs→cr∑sβr,sSs,ar(X)=crω1−qr∏s(Xsαr,s),qr=∑sαr,s.(1)\sum_s \alpha_{r,s}S_s \xrightarrow{c_r} \sum_s \beta_{r,s}S_s,\qquad a_r(X)=c_r\omega^{1-q_r}\prod_s\binom{X_s}{\alpha_{r,s}},\qquad q_r=\sum_s\alpha_{r,s}. \tag*{(1)}

The propensity ar(X)a_r(X) is the transition rate from state XX to state X+βr−αrX+\boldsymbol{\beta}_r-\boldsymbol{\alpha}_r. Here qrq_r is the reaction order, and the binomial factors count the distinct combinations of reactant molecules available in state XX [12], with combinatorial rate factors absorbed into crc_r.

The probability flux through reaction rr out of state XX is the product ar(X)p(X,t)a_r(X)p(X,t). Summing incoming fluxes from predecessor states X−βr+αrX-\boldsymbol{\beta}_r+\boldsymbol{\alpha}_r and subtracting outgoing fluxes gives the master equation

ddtp(X,t)=∑r[ar(X−βr+αr)p(X−βr+αr,t)−ar(X)p(X,t)],(2)\frac{d}{dt}p(X,t)=\sum_r\left[a_r(X-\boldsymbol{\beta}_r+\boldsymbol{\alpha}_r)p(X-\boldsymbol{\beta}_r+\boldsymbol{\alpha}_r,t)-a_r(X)p(X,t)\right], \tag*{(2)}

where terms with negative molecular counts are omitted. Although the propensities ar(X)a_r(X) depend nonlinearly on the counts when qr>1q_r>1, the balance (2) is linear in the probabilities. Enumerating the states as X(i)X^{(i)} and letting pi(t)=p(X(i),t)p_i(t)=p(X^{(i)},t) gives the matrix equation

p˙=Ap,1TA=0,(3)\dot{\boldsymbol{p}}=\mathbf{A}\boldsymbol{p},\qquad\mathbf{1}^{\mathsf{T}}\mathbf{A}=0, \tag*{(3)}

where 1\mathbf{1} is the vector of ones and A\mathbf{A} is the Markov generator. Column ii of A\mathbf{A} collects the outgoing transitions from source state X(i)X^{(i)}, with entries

Aji=∑r:X(j)=X(i)+βr−αrar(X(i))(j≠i),Aii=−∑j≠iAji.A_{ji}=\sum_{r:X^{(j)}=X^{(i)}+\boldsymbol{\beta}_r-\boldsymbol{\alpha}_r}a_r(X^{(i)})\quad(j\ne i),\qquad A_{ii}=-\sum_{j\ne i}A_{ji}.

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 NvN_v well-mixed voxels with positive volumes ωv\omega_v. Since each voxel contains the same NsN_s species, a spatial state is the count array

X=(Xv,s)=(X1,1⋯X1,Ns⋮⋮XNv,1⋯XNv,Ns)∈N0Nv×Ns.(4)X=(X_{v,s})=\begin{pmatrix} X_{1,1} & \cdots& X_{1,N_s} \\ \vdots& & \vdots\\ X_{N_v,1} & \cdots& X_{N_v,N_s} \end{pmatrix}\in\mathbb{N}_0^{N_v\times N_s}. \tag*{(4)}

The probability p(X,t)p(X,t) belongs to this complete array, whose rows specify the molecular counts in individual voxels. Summing p(X,t)p(X,t) over all rows except row vv yields the marginal distribution in voxel vv, 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 rr in voxel vv changes Xv,sX_{v,s} to Xv,s+βr,s−αr,sX_{v,s}+\beta_{r,s}-\alpha_{r,s} for each species while leaving all other rows unchanged, with propensity

ar,v(X)=crωv1−qr∏s(Xv,sαr,s).(5)a_{r,v}(X)=c_r\omega_v^{1-q_r}\prod_s\binom{X_{v,s}}{\alpha_{r,s}}. \tag*{(5)}

Diffusive jumps couple two adjacent rows by transferring one molecule of species ss from voxel vv to a neighboring voxel ww. Each directed edge (v,w)(v,w) and species ss gives the first-order transition Sv,s→Sw,sS_{v,s}\to S_{w,s} acting on (Xv,s,Xw,s)(X_{v,s},X_{w,s}) by

(Xv,s,Xw,s)⟶(Xv,s−1,Xw,s+1)at rate dvw(s)Xv,s.(X_{v,s},X_{w,s})\longrightarrow(X_{v,s}-1,X_{w,s}+1)\quad\text{at rate }d_{vw}^{(s)}X_{v,s}.

The reverse jump from ww to vv occurs at rate dwv(s)d_{wv}^{(s)} per molecule, which may differ from dvw(s)d_{vw}^{(s)} when voxel volumes are unequal. Summing the reaction and diffusion fluxes according to (2) gives the spatial master equation p˙=Ap\dot{p}=Ap. Each configuration has NvNsN_vN_s 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 X\mathcal{X} and evolve its probability entries by the finite state projection [19]. In our multigrid construction, retention is specified by the species totals ks=∑vXv,sk_s=\sum_v X_{v,s}. All spatial arrangements sharing the same totals k=(ks)k=(k_s) form a population block, and X\mathcal{X} is chosen as a finite union of complete population blocks. Because diffusive jumps conserve every species total ksk_s, no diffusion transition can leave X\mathcal{X}. Only reaction channels that change the species totals can cross the truncation boundary. For one species truncated at maximum population Nmax⁡N_{\max}, the retained state space is

X={X∈N0Nv:∑vXv≤Nmax⁡},N=∣X∣=(Nv+Nmax⁡Nmax⁡).(6)\mathcal{X}=\left\{X\in\mathbb{N}_0^{N_v}:\sum_v X_v\le N_{\max}\right\},\qquad N=|\mathcal{X}|=\binom{N_v+N_{\max}}{N_{\max}}. \tag*{(6)}

Bounding the total population ∑vXv\sum_v X_v rather than capping each voxel count XvX_v separately makes X\mathcal{X} closed under diffusion. Restricting the generator to the principal submatrix on these NN states gives the finite evolution equation

p˙=Ap,1TA≤0,(7)\dot{p}=Ap,\qquad\mathbf{1}^{\mathsf{T}}A\le0, \tag*{(7)}

where A\mathbf{A} and p\mathbf{p} henceforth denote the retained generator and probability vector. Omitting a destination state outside X\mathcal{X} removes its off-diagonal entry while leaving its outgoing rate in the source diagonal entry AiiA_{ii}, so escaping probability mass is absorbed rather than reflected to a boundary state.

For a nonexplosive Markov chain whose initial distribution is supported in X\mathcal{X}, the exact solution of (7) extended by zero outside X\mathcal{X} has ℓ1\ell_1 truncation error 1−1⊤p(t)1-\mathbf{1}^{\top}\mathbf{p}(t) [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 X\mathcal{X} 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 pj≈p(jΔt)\mathbf{p}^{j}\approx\mathbf{p}(j\Delta t) for step size Δt>0\Delta t>0. Both backward Euler and Crank–Nicolson advance pj−1\mathbf{p}^{j-1} to x=pj\mathbf{x}=\mathbf{p}^{j} by solving

Aσx=b,Aσ=σI−A,σ>0,(8)A_{\sigma}x=b,\qquad A_{\sigma}=\sigma I-A,\qquad\sigma>0, \tag*{(8)}

where the shift σ\sigma and right-hand side bb are given by

σbbackward Euler1/Δtpj−1/ΔtCrank–Nicolson2/Δt(2/Δt)pj−1+Apj−1(9)\begin{array}{c|c|c} & \sigma& b\\ \text{backward Euler} & 1/\Delta t & p^{j-1}/\Delta t\\ \text{Crank--Nicolson} & 2/\Delta t & (2/\Delta t)p^{j-1}+Ap^{j-1} \tag*{(9)} \end{array}

Here lowercase xx denotes a vector on X\mathcal{X}, while uppercase XX denotes a molecular count configuration. Because AA has nonnegative off-diagonal entries and nonpositive column sums, AσA_{\sigma} is a nonsingular MM-matrix with column sums bounded below by σ>0\sigma>0. Each iterative solve starts from the preceding distribution pj−1\mathbf{p}^{j-1} 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 Δt/2\Delta t/2. Both half-steps and the subsequent Crank–Nicolson steps share the shift σ=2/Δt\sigma=2/\Delta t, 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 xx. The discrepancy of xx in (8) is the residual rr, and the unknown algebraic error ee satisfies the residual equation

r=b−Aσx,e=Aσ−1b−x,Aσe=r.r=b-A_{\sigma}x,\qquad e=A_{\sigma}^{-1}b-x,\qquad A_{\sigma}e=r.

Although ee is unknown, the residual rr is directly computable from xx, bb, and AσA_{\sigma}. Multigrid approximates ee 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 AdA_{\mathrm{d}} inside AA, whose transitions connect molecular arrangements sharing the same species totals. When the diffusive jump rates are reversible with respect to voxel volumes, AdA_{\mathrm{d}} admits positive equilibrium weights πi\pi_i on each population block satisfying πi(Ad)ij=πj(Ad)ji\pi_i(A_{\mathrm{d}})_{ij}=\pi_j(A_{\mathrm{d}})_{ji}. Section 4.2 constructs these weights explicitly from the voxel volumes without assuming equilibrium for the reacting system. Because the equilibrium weights πi\pi_i vary across arrangements, we measure smoothness of an error vector ee through its relative entries fi=ei/πif_i=e_i/\pi_i. The associated graph Dirichlet energy and weighted norm are

12∑i≠jπi(Ad)ji(fi−fj)2,∥e∥π−12=∑iei2πi.(10)\frac{1}{2}\sum_{i\ne j}\pi_i(\mathrm{A}_{\mathrm{d}})_{ji}(f_i-f_j)^2,\qquad\lVert e\rVert_{\pi^{-1}}^2=\sum_i\frac{e_i^2}{\pi_i}. \tag*{(10)}

This graph energy is small when the relative error ff varies slowly across diffusive jumps. For an eigenmode of −Ad-\mathrm{A}_{\mathrm{d}}, its graph energy divided by ∥e∥π−12\lVert e\rVert_{\pi^{-1}}^2 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 fif_i 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.

Hierarchy for one species from a four-voxel RDME to a one-voxel CME

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 k=2k = 2. 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 CkC_k, called aggregates. Each aggregate CkC_k forms one coarse voxel with volume and species counts

Ωk=∑v∈Ckωv,Xk,sc(X)=∑v∈CkXv,s.(11)\Omega_k=\sum_{v\in C_k}\omega_v,\qquad X^{\mathrm{c}}_{k,s}(X)=\sum_{v\in C_k}X_{v,s}. \tag*{(11)}

Let Xc(X)X^{\mathrm{c}}(X) denote the resulting coarse configuration and let Xc={Xc(X):X∈X}\mathcal{X}_{\mathrm{c}}=\{X^{\mathrm{c}}(X):X\in\mathcal{X}\} denote the coarse state space, with dimension Nc=∣Xc∣N_{\mathrm{c}}=\lvert\mathcal{X}_{\mathrm{c}}\rvert. Enumerating the fine and coarse states as X(i)X^{(i)} and Xc,(j)X^{\mathrm{c},(j)}, 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 R∈RNc×NR\in\mathbb{R}^{N_{\mathrm{c}}\times N} acts by

(Rx)j=∑i:Xc(X(i))=Xc,(j)xi,Rji={1,Xc(X(i))=Xc,(j),0,otherwise.(12)(Rx)_j=\sum_{i:X^{\mathrm{c}}(X^{(i)})=X^{\mathrm{c},(j)}}x_i,\qquad R_{ji}= \begin{cases} 1,&X^{\mathrm{c}}(X^{(i)})=X^{\mathrm{c},(j)},\\ 0,&\text{otherwise}. \end{cases} \tag*{(12)}

Applied to a fine probability distribution p\mathbf{p}, restriction computes the exact coarse marginal distribution pc=Rp\mathbf{p}_{\mathrm{c}}=R\mathbf{p}. Within a multigrid cycle, RR acts on the fine residual r\mathbf{r}, summing its signed entries over each coarse equivalence class.

Summing counts over each aggregate preserves the global species totals ks=∑vXv,sk_s = \sum_v X_{v,s} while removing distinctions between internal voxel arrangements. The construction permits any partition into connected aggregates, and our Cartesian experiments group 2d2^d adjacent voxels in dd dimensions.

Prolongation to Fine Arrangements

To distribute a coarse correction among fine arrangements with prescribed aggregate counts, we place the Xk,scX^{c}_{k,s} molecules of species ss in aggregate CkC_k independently across its constituent voxels, choosing v∈Ckv \in C_k with probability ωv/Ωk\omega_v/\Omega_k. 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 X=X(i)X = X^{(i)} and coarse state Xc=Xc,(j)X^c = X^{c,(j)}, the prolongation weight

Pij=∏k,s[Xk,sc!∏v∈CkXv,s!∏v∈Ck(ωvΩk)Xv,s]if Xc(X)=Xc,(13)P_{ij} = \prod_{k,s} \left[ \frac{X^c_{k,s}!}{\prod_{v\in C_k} X_{v,s}!} \prod_{v\in C_k} \left(\frac{\omega_v}{\Omega_k}\right)^{X_{v,s}} \right] \quad\text{if } X^c(X) = X^c, \tag*{(13)}

and Pij=0P_{ij}=0 otherwise. The weight factors across aggregates and species because their placements are independent. § 1.4.2 shows that PijP_{ij} 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 xc∈RNcx_c \in\mathbb{R}^{N_c}, prolongation P∈RN×NcP \in\mathbb{R}^{N \times N_c} acts by

(Pxc)i=∑jPij(xc)j.(14)(Px_c)_i = \sum_j P_{ij}(x_c)_j. \tag*{(14)}

Each column of RR contains a single nonzero entry equal to one, and each row of PP contains a single nonzero entry equal to its multinomial weight PijP_{ij}.

Because the transfer operators preserve species totals, ordering states by total population and then grouping fine states by their coarse image Xc,(j)X^{c,(j)} puts both matrices into block-diagonal form. Letting wjw_j denote the column vector of multinomial weights (13) for fine states in class jj, this ordering gives

R=(1T0⋯01T⋯⋮⋮⋱),P=(w10⋯0w2⋯⋮⋮⋱).(15)R = \begin{pmatrix} \mathbf{1}^{\mathsf{T}} & 0 & \cdots\\ 0 & \mathbf{1}^{\mathsf{T}} & \cdots\\ \vdots& \vdots& \ddots \end{pmatrix}, \qquad P = \begin{pmatrix} w_1 & 0 & \cdots\\ 0 & w_2 & \cdots\\ \vdots& \vdots& \ddots \end{pmatrix}. \tag*{(15)}

In each block jj, the row vector 1T\mathbf{1}^{\mathsf{T}} sums the entries of the compatible fine arrangements, and the column vector wjw_j distributes the coarse correction across them with 1Twj=1\mathbf{1}^{\mathsf{T}}w_j = 1, as illustrated in Figure 2.

Transfer operations for restriction and prolongation

Figure 2. The transfer operations for one species with coarse state Xc=(2,0)X^c=(2,0) at index jj on four voxels of equal volume with aggregates {v1,v2}\{v_1,v_2\} and {v3,v4}\{v_3,v_4\}. 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 PP sum to unity by the multinomial theorem, the transfer operators satisfy

RP=I,1TR=1T,1TP=1T,(16)RP = I,\qquad\mathbf{1}^{\mathsf{T}}R = \mathbf{1}^{\mathsf{T}},\qquad\mathbf{1}^{\mathsf{T}}P = \mathbf{1}^{\mathsf{T}}, \tag*{(16)}

where each vector 1\mathbf{1} has compatible dimension. Restriction therefore recovers any prolonged coarse vector, and (PR)2=P(RP)R=PR(PR)^2 = P(RP)R = PR makes PRPR a projection on the fine space.

Coarse Correction

A coarse-level correction has the prolonged form PecPe_c, and its action on the restricted residual is RAσPecRA_\sigma Pe_c. Requiring this term to cancel the restricted residual RrRr determines the Galerkin coarse system and fine update

Aσ,cec=Rr,x+=x+Pec,Aσ,c=RAσP.(17)A_{\sigma,c}e_c = Rr,\qquad x^+ = x + Pe_c,\qquad A_{\sigma,c} = RA_\sigma P. \tag*{(17)}

The coarse correction ece_c has signed entries. An exact coarse solve annihilates the restricted residual,

R(b−Aσx+)=Rr−Aσ,cec=0,R(b-A_\sigma x^+) = Rr-A_{\sigma,c}e_c = 0,

so the updated iterate x+x^{+} satisfies the fine equation after summation over each coarse count class. Because RP=IRP=I implies (I−PR)P=0(I-PR)P=0, the update also preserves the fine component omitted by restriction,

(I−PR)x+=(I−PR)x,(18)(I-PR)x^{+}=(I-PR)x, \tag*{(18)}

adding a coarse correction without replacing the fine iterate by a multinomial distribution. Relaxation damps error components in the null space of RR before and after (17).

Coarse Equations

To apply (17) recursively across multiple levels, we assemble the Galerkin coarse generator

Ac=RAP.(19)A_{\mathrm{c}}=RAP. \tag*{(19)}

For distinct coarse states j≠kj\ne k, expanding the matrix product shows that (Ac)jk(A_{\mathrm{c}})_{jk} averages all fine transition rates leading from class kk to class jj,

(Ac)jk=∑i:Rki=1Pik∑m:Rjm=1Ami,j≠k.(20)(A_{\mathrm{c}})_{jk}=\sum_{i:R_{ki}=1}P_{ik}\sum_{m:R_{jm}=1}A_{mi},\qquad j\ne k. \tag*{(20)}

Evaluating these averages analytically yields closed-form coarse diffusion and reaction propensities without forming the sparse matrix product RAPRAP.

For diffusion (suppressing the species index), a molecule in aggregate CkC_k occupies fine voxel v∈Ckv\in C_k with marginal probability ωv/Ωk\omega_v/\Omega_k under (13), so its expected jump rate per molecule into another aggregate CjC_j (j≠kj\ne k) is

dkjc=∑v∈CkωvΩk∑w∈Cjdvw,k≠j,(21)d^{\mathrm{c}}_{kj}=\sum_{v\in C_k}\frac{\omega_v}{\Omega_k}\sum_{w\in C_j}d_{vw},\qquad k\ne j, \tag*{(21)}

with coarse diffusive propensity dkjcXkcd^{\mathrm{c}}_{kj}X^{\mathrm{c}}_k. 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 dd-dimensional Cartesian grid of spacing hh and jump rate D/h2D/h^2 coarsened by grouping 2d2^d voxels per aggregate, adjacent aggregates share 2d−12^{d-1} fine interface edges with ωv/Ωk=2−d\omega_v/\Omega_k=2^{-d}, so (21) gives dkjc=2D/(2h)2d^{\mathrm{c}}_{kj}=2D/(2h)^2, which is twice the naive coarse finite-difference rate D/(2h)2D/(2h)^2.

If the reaction rate constant crc_r is uniform across the fine voxels of aggregate CkC_k, the corresponding coarse reaction propensity is

ar,kc(Xc)=crΩk1−qr∏s(Xk,scαr,s).(22)a^{\mathrm{c}}_{r,k}(X^{\mathrm{c}})=c_r\Omega_k^{1-q_r}\prod_s\left(\frac{X^{\mathrm{c}}_{k,s}}{\alpha_{r,s}}\right). \tag*{(22)}

Theorem 4.1 proves that (21) and (22), together with absorbing losses at omitted destination states, reproduce the Galerkin generator Ac=RAPA_{\mathrm{c}}=RAP.

Because AcA_{\mathrm{c}} retains the algebraic form of an RDME generator on the aggregate voxel graph, repeating the construction across NlN_l coarsening steps gives the level generators

A0=A,Al+1=RlAlPl,l=0,…,Nl−1,(23)A_0=A,\qquad A_{l+1}=R_lA_lP_l,\qquad l=0,\ldots,N_l-1, \tag*{(23)}

provided each reaction rate constant crc_r is uniform within every aggregate at every level. The bottom level NlN_l has a single voxel of volume Ω=∑vωv\Omega=\sum_v\omega_v and no diffusion, reducing to a well-mixed CME on the species totals with Nmax⁡+1N_{\max}+1 unknowns for one species at cap Nmax⁡N_{\max}. By (16), the shifted coarse operators satisfy

Aσ,c=R(σI−A)P=σI−Ac,(24)A_{\sigma,\mathrm{c}}=R(\sigma I-A)P=\sigma I-A_{\mathrm{c}}, \tag*{(24)}

so the same generator hierarchy {Al}l=0Nl\{A_l\}_{l=0}^{N_l} applies at every positive shift σ\sigma.

Smoothing

Because a coarse correction PecP e_c lies in the column space of PP, it cannot independently adjust relative errors among fine arrangements that share the same coarse counts. Relaxation sweeps on Aσx=bA_\sigma x=b supply these local updates before and after coarse correction. We apply point or approximate block Gauss–Seidel to the complete shifted matrix AσA_\sigma, including reactions, diffusion, absorbing losses, and the shift. Point Gauss–Seidel updates one state component at a time via

xi←xi+bi−(Aσx)i(Aσ)ii,(25)x_i \leftarrow x_i + \frac{b_i-(A_\sigma x)_i}{(A_\sigma)_{ii}}, \tag*{(25)}

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 k=∑vXvk=\sum_v X_v while reactions change kk by ±1\pm1, so ordering states by k=0,…,Nmax⁡k=0,\ldots,N_{\max} makes AσA_\sigma block tridiagonal. Letting xkx_k and bkb_k denote the subvectors for population kk, approximate block Gauss–Seidel updates each population block in turn via

rk=bk−∑j=k−1k+1(Aσ)kjxj,xk←xk+A~σ,k−1rk,(26)r_k=b_k-\sum_{j=k-1}^{k+1}(A_\sigma)_{kj}x_j,\qquad x_k\leftarrow x_k+\widetilde{A}_{\sigma,k}^{-1}r_k, \tag*{(26)}

where A~σ,k\widetilde{A}_{\sigma,k} is the zero-fill incomplete LU factorization, denoted ILU(0), of the diagonal block (Aσ)kk(A_\sigma)_{kk} [21] and indices outside 0,…,Nmax⁡0,\ldots,N_{\max} are omitted. The default block smoother applies one forward sweep before coarse correction and one reverse sweep afterward. On the bottom CME level l=Nll=N_l, 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 RlR_l, PlP_l, and AlA_l 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 ll with a recursive coarse correction on level l+1l+1. Let Cycle⁡(l,b)\operatorname{Cycle}(l,b) denote one cycle for Aσ,lx=bA_{\sigma,l}x=b starting from a zero initial guess, where Aσ,l=σI−AlA_{\sigma,l}=\sigma I-A_l. After forward relaxation of xx on level ll and restriction of the residual bc=Rl(b−Aσ,lx)b_c=R_l(b-A_{\sigma,l}x), the V- and W-cycles compute ece_c by

ec(0)=0,ec(j+1)=ec(j)+Cycle⁡(l+1,bc−Aσ,l+1ec(j)),(27)e_c^{(0)}=0,\qquad e_c^{(j+1)}=e_c^{(j)}+\operatorname{Cycle}(l+1,b_c-A_{\sigma,l+1}e_c^{(j)}), \tag*{(27)}

performing one recursive step (ec=ec(1)e_c=e_c^{(1)}) in a V-cycle and two recursive steps (ec=ec(2)e_c=e_c^{(2)}) in a W-cycle [27].

The K-cycle instead minimizes the coarse residual norm ∥bc−Aσ,l+1ec∥2\lVert b_c-A_{\sigma,l+1}e_c\rVert_2 over at most two recursive directions [20]. It first scales the initial recursive direction v1=Cycle⁡(l+1,bc)v_1=\operatorname{Cycle}(l+1,b_c) to minimize the coarse residual norm along v1v_1. 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 l=Nll = N_l, 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 xx from the preceding probability distribution and apply

x←x+Cycle⁡(0,b−Aσ,0x)x \leftarrow x + \operatorname{Cycle}(0, b - A_{\sigma,0}x)

until ∥b−Aσ,0x∥1/σ≤ε\lVert b - A_{\sigma,0}x\rVert_1/\sigma\le\varepsilon. Proposition 4.4 shows that this stopping rule bounds the ℓ1\ell_1 algebraic error ∥x−Aσ,0−1b∥1\lVert x - A_{\sigma,0}^{-1}b\rVert_1 by ε\varepsilon using only the computable fine residual. Time discretization and FSP truncation errors are assessed separately.

Applying RlR_l or PlP_l requires O(Nl)O(N_l) work, and a point sweep or an application of stored ILU(0) factors requires O(nnz⁡(Aσ,l))O(\operatorname{nnz}(A_{\sigma,l})) work. For one species on a dd-dimensional Cartesian hierarchy at fixed cap Nmax⁡≥1N_{\max} \ge1, summing this work across levels yields O(N)O(N) cost per V-, W-, or K-cycle when dNmax⁡>1dN_{\max} > 1, with an additional logarithmic factor O(Nlog⁡N)O(N \log N) for W- and K-cycles when d=Nmax⁡=1d = N_{\max} = 1 (Supplementary Section S2.3). Level matrices and ILU(0) factors are reused while σ\sigma is unchanged, and existing diagonal blocks are preserved when adaptive FSP increases Nmax⁡N_{\max} (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 NlN_l on each level rather than sparse transfer matrices. For fine state X(i)X^{(i)}, parent[i] records the coarse index jj of Xc(X(i))X^c(X^{(i)}), and weight[i] stores its multinomial weight PijP_{ij}, encoding

Rparent⁡[i],i=1,Pi,parent⁡[i]=weight⁡[i],(28)R_{\operatorname{parent}[i],i} = 1,\qquad P_{i,\operatorname{parent}[i]} = \operatorname{weight}[i], \tag*{(28)}

with all other entries zero. Algorithm 3.3 builds these arrays once during setup, evaluating factorials through their logarithms and normalizing each column of PP 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

  1. Given the retained states, p(0)\boldsymbol{p}(0), final time TT, step lengths, time integration method, cycle type, and tolerance ε\varepsilon.

  2. Construct the voxel hierarchy down to one voxel and its transfers by Algorithm 3.3, and form the generators AlA_l using (19).

  3. Initialize t←0t \leftarrow0 and p←p(0)\boldsymbol{p} \leftarrow\boldsymbol{p}(0).

  4. for each prescribed step of length Δt\Delta t up to TT do

  5. Form σ\sigma and b\boldsymbol{b} from p\boldsymbol{p} using (9).

  6. Form Aσ,l=σI−AlA_{\sigma,l} = \sigma I - A_l, relaxation factors, and the bottom factorization, reusing them when σ\sigma is unchanged.

  7. Initialize x←p\boldsymbol{x} \leftarrow\boldsymbol{p} and r←b−Aσ,0x\boldsymbol{r} \leftarrow\boldsymbol{b} - A_{\sigma,0}\boldsymbol{x}.

  8. while ∥r∥1/σ>ε\lVert\boldsymbol{r}\rVert_1/\sigma> \varepsilon do

  9. x←x+Cycle⁡(0,r)\boldsymbol{x} \leftarrow\boldsymbol{x} + \operatorname{Cycle}(0,\boldsymbol{r}) using Algorithm 3.2.

  10. r←b−Aσ,0x\boldsymbol{r} \leftarrow\boldsymbol{b} - A_{\sigma,0}\boldsymbol{x}.

  11. end while

  12. Accept p←x\boldsymbol{p} \leftarrow\boldsymbol{x} and advance t←t+Δtt \leftarrow t + \Delta t.

  13. end for

  14. return the fine probability distribution p\boldsymbol{p} at TT.

Algorithm 3.2 One multigrid cycle Cycle⁡(l,b)\operatorname{Cycle}(l,\boldsymbol{b})

  1. Input level ll and right-hand side b\boldsymbol{b}, and initialize x←0\boldsymbol{x} \leftarrow0.

  2. if l=Nll = N_l (one-voxel CME) then

  3. return Aσ,Nl−1bA_{\sigma,N_l}^{-1}\boldsymbol{b} by the bottom direct solve.

  4. end if

  5. Apply forward relaxation to Aσ,lx=bA_{\sigma,l}\boldsymbol{x} = \boldsymbol{b}.

  6. Form r←b−Aσ,lx\boldsymbol{r} \leftarrow\boldsymbol{b} - A_{\sigma,l}\boldsymbol{x} and restrict bc←Rlr\boldsymbol{b}_c \leftarrow R_l\boldsymbol{r} using Algorithm 3.4.

  7. Recurse toward the CME to compute ec\boldsymbol{e}_c by (27) for the V- or W-cycle, or by residual minimization for the K-cycle.

  8. Prolong and add x←x+Plec\boldsymbol{x} \leftarrow\boldsymbol{x} + P_l\boldsymbol{e}_c using Algorithm 3.5.

  9. Apply reverse relaxation to Aσ,lx=bA_{\sigma,l}\boldsymbol{x} = \boldsymbol{b} and return x\boldsymbol{x}.

Algorithm 3.3 Construct restriction and prolongation for adjacent levels

  1. Given fine and coarse state lists, aggregates CkC_k, and volumes, initialize sum⁡[j]←0\operatorname{sum}[j] \leftarrow0 for every coarse index jj.

  2. for each fine state XX with index ii do

  3. Xk,sc←∑v∈CkXv,sX^c_{k,s} \leftarrow\sum_{v\in C_k} X_{v,s} for every aggregate and species.

  4. Let jj be the index of XcX^c in the coarse state list, with parent⁡[i]←j\operatorname{parent}[i] \leftarrow j.

  5. weight⁡[i]←∏k,s[Xk,sc!∏v∈CkXv,s!∏v∈Ck(ωvΩk)Xv,s]\operatorname{weight}[i] \leftarrow\prod_{k,s}\left[\frac{X^c_{k,s}!}{\prod_{v\in C_k}X_{v,s}!}\prod_{v\in C_k}\left(\frac{\omega_v}{\Omega_k}\right)^{X_{v,s}}\right]

  6. sum⁡[j]←sum⁡[j]+weight⁡[i]\operatorname{sum}[j] \leftarrow\operatorname{sum}[j]+\operatorname{weight}[i].

  7. end for

  8. for each fine index ii do

  9. weight⁡[i]←weight⁡[i]/sum⁡[parent⁡[i]]\operatorname{weight}[i] \leftarrow\operatorname{weight}[i]/\operatorname{sum}[\operatorname{parent}[i]].

  10. end for

  11. 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 Ac=RAP\mathbf{A}_c = R\mathbf{A}P. We then characterize the fine error omitted by the coarse projection PRPR under reversible diffusion, showing that PRPR 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 ℓ1\ell_1 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 j≠kj \ne k, the off-diagonal sum in (20) is nonnegative because the two fine classes are disjoint and Pik≥0P_{ik} \ge0. Moreover, (16) and 1TA≤0\mathbf{1}^{\mathsf{T}}\mathbf{A} \le0 imply 1TAc=1TAP≤0\mathbf{1}^{\mathsf{T}}\mathbf{A}_c = \mathbf{1}^{\mathsf{T}}\mathbf{A}P \le0, so Ac\mathbf{A}_c 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 X\mathcal{X} contains complete population blocks and crc_r is uniform within each aggregate, then the reaction part of Ac=RAP\mathbf{A}_c = R\mathbf{A}P has propensity (22), including losses to omitted destination states.

Diffusion and the Coarse Approximation

We now construct the equilibrium weights πi\pi_i 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 ωvw(s)=ωwv(s)\omega_{vw}^{(s)} = \omega_{wv}^{(s)}. Because diffusion preserves each species total, every population block is a finite closed communicating class of Ad\mathbf{A}_d. For one species at total population kk, the multinomial distribution

π(X)=k!∏vXv!∏v(ωvΩ)Xv,Ω=∑vωv(29)\pi(X) = \frac{k!}{\prod_v X_v!}\prod_v\left(\frac{\omega_v}{\Omega}\right)^{X_v}, \qquad\Omega= \sum_v \omega_v \tag*{(29)}

assigns positive weight to each arrangement and sums to one by the multinomial theorem. For a jump X→X′X \to X' moving one molecule from voxel vv to voxel ww, the weights satisfy

π(X′)π(X)=XvXw+1ωwωv,π(X)dvwXv=π(X′)dwv(Xw+1),\frac{\pi(X')}{\pi(X)} = \frac{X_v}{X_w+1}\frac{\omega_w}{\omega_v}, \qquad\pi(X)d_{vw}X_v = \pi(X')d_{wv}(X_w+1),

equating the forward and reverse equilibrium fluxes across every edge and implying stationarity under Ad\mathbf{A}_{\mathrm{d}}. 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 m(k)>0m(k)>0 without requiring an equilibrium assumption for the reaction channels.

Letting πi=π(X(i))\pi_i=\pi(X^{(i)}) and Π=diag⁡(π)\mathbf{\Pi}=\operatorname{diag}(\pi), detailed balance and stationarity read

πi(Ad)ji=πj(Ad)ij,Adπ=0,\pi_i(\mathbf{A}_{\mathrm{d}})_{ji}=\pi_j(\mathbf{A}_{\mathrm{d}})_{ij},\qquad\mathbf{A}_{\mathrm{d}}\pi=0,

so multiplying Ad\mathbf{A}_{\mathrm{d}} on the right by Π\mathbf{\Pi} produces a symmetric positive semidefinite graph Laplacian [1, 6],

L=−AdΠ,(30)\mathbf{L}=-\mathbf{A}_{\mathrm{d}}\mathbf{\Pi}, \tag*{(30)}

with nonpositive off-diagonal entries and zero row sums. Writing an error vector ee in terms of its relative entries fi=ei/πif_i=e_i/\pi_i as e=Πfe=\mathbf{\Pi}f, pure diffusion e˙=Ade\dot{e}=\mathbf{A}_{\mathrm{d}}e takes the form

f˙i=∑j≠i(Ad)ji(fj−fi),Πf˙=−Lf,\dot{f}_i=\sum_{j\ne i}(\mathbf{A}_{\mathrm{d}})_{ji}(f_j-f_i),\qquad\mathbf{\Pi}\dot{f}=-\mathbf{L}f,

and differentiating ∥e∥π−12=fTΠf\lVert e\rVert_{\pi^{-1}}^2=f^{\mathsf{T}}\mathbf{\Pi}f yields the energy dissipation identity

12ddt∥e∥π−12=−fTLf=−12∑i≠jπi(Ad)ji(fi−fj)2,\frac{1}{2}\frac{\mathrm{d}}{\mathrm{d}t}\lVert e\rVert_{\pi^{-1}}^2=-f^{\mathsf{T}}\mathbf{L}f=-\frac{1}{2}\sum_{i\ne j}\pi_i(\mathbf{A}_{\mathrm{d}})_{ji}(f_i-f_j)^2,

matching the graph energy in (10). If Lϕ=λΠϕ\mathbf{L}\phi=\lambda\mathbf{\Pi}\phi, then AdΠϕ=−λΠϕ\mathbf{A}_{\mathrm{d}}\mathbf{\Pi}\phi=-\lambda\mathbf{\Pi}\phi and the mode Πϕ\mathbf{\Pi}\phi decays as e−λte^{-\lambda t} with decay rate λ=(ϕTLϕ)/(ϕTΠϕ)\lambda=(\phi^{\mathsf{T}}\mathbf{L}\phi)/(\phi^{\mathsf{T}}\mathbf{\Pi}\phi).

Conditioning the global equilibrium weights πi\pi_i on the coarse aggregate counts recovers the multinomial prolongation weights (13) and characterizes the projection error e−PRee-PRe as a conditional variance.

Lemma 4.2. For reversible diffusion,

Pij=πi(Rπ)jwhen Rji=1,(31)P_{ij}=\frac{\pi_i}{(R\pi)_j}\quad\text{when }R_{ji}=1, \tag*{(31)}

and the error omitted by PRPR satisfies

∥e−PRe∥π−12=∑j∑i:Rji=1πi[fi−(Re)j(Rπ)j]2.(32)\lVert e-PRe\rVert_{\pi^{-1}}^2=\sum_j\sum_{i:R_{ji}=1}\pi_i\left[f_i-\frac{(Re)_j}{(R\pi)_j}\right]^2. \tag*{(32)}

For the represented error PRePRe, the relative entries (PRe)i/πi(PRe)_i/\pi_i equal the conditional average (Re)j/(Rπ)j(Re)_j/(R\pi)_j of fi=ei/πif_i=e_i/\pi_i over all fine states in coarse class jj, and (32) measures the variance lost in this averaging, as illustrated in Figure 3.

Diffusion state graph for one species with $k=3$ on a chain of three voxels

Figure 3. Diffusion state graph for one species with k=3k=3 on a chain of three voxels of equal volume, with aggregates C1={v1,v2}C_1=\{v_1,v_2\} and C2={v3}C_2=\{v_3\}. Each shaded row is one coarse state XcX^c, and PRP^R averages the relative error over the fine states in that row. Solid edges represent jumps inside an aggregate and contribute to EinE_{\mathrm{in}}, 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 Ein(f)E_{\mathrm{in}}(f) 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 λ∗>0\lambda_* > 0 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,

∥e−PRe∥π−12≤λ∗−1Ein(f).\lVert e-PRe\rVert_{\pi^{-1}}^2\le\lambda_*^{-1}E_{\mathrm{in}}(f).

Because λ∗\lambda_* is determined by single-molecule diffusion on each aggregate, the constant λ∗−1\lambda_*^{-1} 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 ℓ1\ell_1 algebraic error in a completed linear solve through the computable fine residual, without requiring reversibility or an equilibrium assumption.

Proposition 4.4. If A\mathbf{A} has nonnegative off-diagonal entries and nonpositive column sums, then for Aσ=σI−A\mathbf{A}_{\sigma}=\sigma\mathbf{I}-\mathbf{A} with σ>0\sigma>0,

∥x−Aσ−1b∥1≤σ−1∥b−Aσx∥1.(33)\lVert x-\mathbf{A}_{\sigma}^{-1}b\rVert_1\leq\sigma^{-1}\lVert b-\mathbf{A}_{\sigma}x\rVert_1. \tag*{(33)}

When ∥b−Aσx∥1/σ≤ε\lVert b-\mathbf{A}_{\sigma}x\rVert_1/\sigma\leq\varepsilon, any marginal probability formed by summing a subset of entries of xx has algebraic error at most ε\varepsilon. 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 XvX_v be the count in voxel vv and k=∑vXvk=\sum_v X_v the total population, whose marginal distribution is obtained by summing probabilities over all states with total kk.

We consider a linear immigration–degradation model with birth propensity 2ωv2\omega_v and death propensity XvX_v, together with the bistable Schlögl system [24], whose birth and death propensities in voxel vv are

a+,v(Xv)=c3ωv+c1ωv(Xv2),a_{+,v}(X_v)=c_3\omega_v+\frac{c_1}{\omega_v}\binom{X_v}{2},
a−,v(Xv)=c4Xv+c2ωv2(Xv3),a_{-,v}(X_v)=c_4X_v+\frac{c_2}{\omega_v^2}\binom{X_v}{3},
(c1,c2,c3,c4)=10−4(133,6,6924.125,1147.25).(c_1,c_2,c_3,c_4)=10^{-4}(133,6,6924.125,1147.25).

For individual linear solves, we let D=1D=1 and b=σp(0)b=\sigma p(0) and initialize the iteration with x=p(0)x=p(0), corresponding to one backward Euler step. The linear model uses σ=0.5\sigma=0.5 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, σ=0.05\sigma=0.05, 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 ε=10−9\varepsilon=10^{-9}. 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 AσA_\sigma 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 σ\sigma 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 4→2→14\to2\to1 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%.

cycleiterationsfinal boundsetupsolveGiB
V1000 (limit)3.36×10−33.36\times10^{-3}13.3342.690.214
W1119.33×10−109.33\times10^{-10}13.366.920.228
K558.87×10−108.87\times10^{-10}13.473.350.223

Table 1. Cycles for the linear problem on 1,024 voxels at cap 2, D=1D=1, and σ=0.5\sigma=0.5, using the same levels and point relaxation. V reaches the iteration limit, whereas W and K meet tolerance 10−910^{-9}. Times are in seconds and peak memory is in GiB, with one run per cycle type.

To test population refinement, we increase Nmax⁡N_{\max} 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.

capstatesCME correctionW-cycle
215321430
44,84535934
674,61345536
8735,47150137

Table 2. Population refinement on 16 voxels for the linear model, D=1D = 1, σ=0.5\sigma= 0.5, with default point relaxation and tolerance 10−910^{-9}. CME correction omits intermediate spatial levels.

For spatial refinement we fix Nmax⁡=2N_{\max} = 2 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 10−910^{-9}, 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.

modelvoxelscapstatescyclestotal time (s)
Schlögl440135,751110 / 400.706 / 0.362
Schlögl460635,376154 / 564.884 / 2.343
linear168735,47150 / 282.888 / 2.265
linear644814,38567 / 484.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 →\to 2 →\to 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 10−910^{-9}, with times in seconds and peak memory in GiB. The linear problem has 1,024 voxels and σ=0.5\sigma= 0.5, while the Schlögl transients on four voxels use T=100T = 100, Δt=5\Delta t = 5, and 21 solves with reused setup. All use D=1D = 1. Point and block WW use their default numbers of sweeps, and a dash denotes direct solution.

methodNmax⁡N_{\max}statescyclessetupsolveGiB
Linear model
KLU2525,825—31.170.191.16
point W2525,82511113.366.920.23
Schlögl transient
point W963,921,22514811.06435.571.02
block W963,921,22510721.56261.471.50
point W1127,160,24514811.74816.721.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 1.2×1081.2 \times10^{8} nonzeros per triangular factor at cap 32 and 5.1×10105.1 \times10^{10} 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 (2,2,2,2)(2, 2, 2, 2) to T=100T = 100 on four voxels with D=1D = 1 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 P(k≥21)\mathbb{P}(k \ge21) above k=20k = 20, and the WW-cycle counts per solve.

Figure 6. Schlögl evolution on four voxels from (2,2,2,2)(2,2,2,2), D=1D=1, Δt=5\Delta t=5, and algebraic tolerance 10−910^{-9}. Panels (a,b) use cap 96 and block W. Panel (c) compares population caps at T=100T=100, and panel (d) compares the number of point and block W-cycles per solve at cap 96.

At T=100T = 100, the distribution exhibits two population modes at k=7k = 7 and k=37k = 37. Increasing the cap from 80 to 96 changes P(k≥21)\mathbb{P}(k \ge21) by 6.42×10−36.42 \times10^{-3}, and increasing it from 96 to 112 (7,160,245 fine states and 113 CME states) changes P(k≥21)\mathbb{P}(k \ge21) by 1.78×10−51.78 \times10^{-5} and the population marginal by 1.85×10−51.85 \times10^{-5} in ℓ1\ell_1 (Table 5). At cap 96, point and block relaxation produce final marginals agreeing to 8.15×10−138.15 \times10^{-13} in ℓ1\ell_1, 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 T=100T = 100, Δt=5\Delta t = 5, with WW and tolerance 10−910^{-9}. The reported mass is subject to errors from time discretization and linear solves.

relaxationNmax⁡N_{\max}statesretained massP(k≥21)\mathbb{P}(k \ge21)
block801,929,5010.99329123740.4491884933
block963,921,2250.99998150480.4556061510
point1127,160,2450.99999999500.4556239278

Table 5.

At cap 112, halving the step size through Δt=5\Delta t = 5, 2.5, and 1.25 gives P(k≥21)=0.4556239278\mathbb{P}(k \ge21) = 0.4556239278, 0.4557196041, and 0.4557434892 in 818, 1,716, and 2,438 seconds, respectively. The successive differences 9.57×10−59.57 \times10^{-5} and 2.39×10−52.39 \times10^{-5} 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 (0,0,0,0)(0, 0, 0, 0) with D=1D = 1 and (c1,c2,c3,c4)=(0.0258,0.0024,0.00138,0.0829)(c_1, c_2, c_3, c_4) = (0.0258, 0.0024, 0.00138, 0.0829), and integrate to T=500T = 500. The resulting population marginal has a dominant mode at k=0k = 0 and a faint secondary peak at k=20k=20 separated by a minimum near k=14k=14 (Figure 7). At cap 72 and Δt=5\Delta t=5 with tolerance 10−1410^{-14} (1,282,975 states), the multigrid FSP solver gives P(k(T)≥16)=1.7746×10−6\mathbb{P}(k(T)\geq16)=1.7746\times10^{-6} and P(k(T)=20)=1.2325×10−7\mathbb{P}(k(T)=20)=1.2325\times10^{-7}. A calculation at cap 56, Δt=10\Delta t=10, and tolerance 10−1310^{-13} (487,635 states) takes 37.4 seconds (66.1 seconds without the intermediate two-voxel level, see Supplementary § 4.4.4) and matches P(k(T)=20)\mathbb{P}(k(T)=20) to within 0.137% (refinements in Supplementary Table S1).

Figure 7. Rare switching at T=500T = 500. Panel (a) compares FSP at cap 72, Δt=5\Delta t = 5, 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, 10610^{6} independent SSA trajectories [11] produce three endpoints with k≥16k\geq16 and none at k=20k=20, while 6×1076\times10^{7} trajectories (673.5 seconds) produce 96 and four endpoints, respectively. Using the relative standard error (1−p)/(mp)\sqrt{(1-p)/(mp)} for mm trajectories, the refined FSP probabilities predict 9.7% relative standard error for P(k(T)≥16)\mathbb{P}(k(T)\geq16) and 50% at k=20k=20. Reaching 10% relative standard error at k=20k=20 with independent SSA paths would require about 8.1×1088.1\times10^{8} 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 10−710^{-7}. 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 EP[⋅∣Xc]\mathbb{E}_{P}[\cdot\mid X^{c}] denote expectation under the prolongation weights (13) conditioned on a coarse state Xc=Xc,(m)X^{c} = X^{c,(m)}. Under (13), the fine count Xv,sX_{v,s} in voxel v∈Ckv \in C_k has a binomial marginal distribution with N=Xk,scN = X^c_{k,s} trials and success probability θ=ωv/Ωk\theta= \omega_v/\Omega_k. For a=αr,s≤Na = \alpha_{r,s} \le N, the identity (na)(Nn)=(Na)(N−an−a)\binom{n}{a}\binom{N}{n} = \binom{N}{a}\binom{N-a}{n-a} gives the factorial moment

EP[(Xv,sαr,s) | Xc]=∑n=aN(na)(Nn)θn(1−θ)N−n=(Na)θa∑n=aN(N−an−a)θn−a(1−θ)N−n=(Xk,scαr,s)(ωvΩk)αr,s.\begin{aligned} \mathbb{E}_{P}\left[\binom{X_{v,s}}{\alpha_{r,s}} \,\middle|\, X^c\right] = \sum_{n=a}^{N} \binom{n}{a}\binom{N}{n}\theta^n(1-\theta)^{N-n} \\ &= \binom{N}{a}\theta^a \sum_{n=a}^{N}\binom{N-a}{n-a}\theta^{n-a}(1-\theta)^{N-n} = \binom{X^c_{k,s}}{\alpha_{r,s}}\left(\frac{\omega_v}{\Omega_k}\right)^{\alpha_{r,s}}. \end{aligned}

which also holds when N<aN<a since both sides vanish. Because the weights [13] factor independently across species and qr=∑sαr,sq_r = \sum_s \alpha_{r,s}, summing [5] over v∈Ckv \in C_k yields

∑v∈CkEP[ar,v(X)∣Xc]=∑v∈Ckcrωv1−qr∏s[(Xk,scαr,s)(ωvΩk)αr,s]=crΩk−qr(∑v∈Ckωv)∏s(Xk,scαr,s)=ar,kc(Xc).\begin{aligned} \sum_{v\in C_k}\mathbb{E}_{P}[a_{r,v}(X)\mid X^c] = \sum_{v\in C_k}c_r\omega_v^{1-q_r}\prod_s\left[\binom{X^c_{k,s}}{\alpha_{r,s}}\left(\frac{\omega_v}{\Omega_k}\right)^{\alpha_{r,s}}\right] \\ &= c_r\Omega_k^{-q_r}\left(\sum_{v\in C_k}\omega_v\right)\prod_s\binom{X^c_{k,s}}{\alpha_{r,s}} = a^c_{r,k}(X^c). \end{aligned}

Every occurrence of reaction rr at any fine voxel v∈Ckv \in C_k produces the same coarse state change βr−αr\beta_r-\alpha_r in row kk of XcX^c. Because X\mathcal{X} is a union of complete population blocks, a fine destination state belongs to X\mathcal{X} if and only if its coarse destination belongs to Xc\mathcal{X}^c. An omitted destination state therefore leaves the averaged loss −ar,kc(Xc)-a^c_{r,k}(X^c) on the diagonal of AcA_c without a matching off-diagonal entry. □

Proof of Lemma 4.2. Consider a coarse state Xc=Xc,(j)X^c = X^{c,(j)} at index jj with species totals ks=∑hXh,sck_s = \sum_h X^c_{h,s}. Let m(k)>0m(k)>0 be the positive weight assigned to population block k=(ks)k=(k_s) and Ω=∑vωv\Omega= \sum_v\omega_v. Regrouping the equilibrium weights (29) by aggregate and comparing with [13] gives, for every fine state X(i)X^{(i)} with Rji=1R_{ji}=1,

πi=m(k)∏sks!Ωkks∏h,sΩhXh,scXh,sc!Pij.\pi_i = m(k)\prod_s\frac{k_s!}{\Omega_k^{k_s}}\prod_{h,s}\frac{\Omega_h^{X^c_{h,s}}}{X^c_{h,s}!}P_{ij}.

The positive factor preceding PijP_{ij} depends only on the coarse state XcX^c. Because X\mathcal{X} retains complete population blocks, the multinomial theorem implies ∑i:Rji=1Pij=1\sum_{i:R_{ji}=1}P_{ij}=1. Summing the factorization of πi\pi_i over {i:Rji=1}\{i:R_{ji}=1\} therefore identifies the prefactor as (Rπ)j(R\pi)_j, and dividing by (Rπ)j(R\pi)_j establishes (31) with m(k)m(k) canceling from the ratio.

For each fine index ii, let jj be its unique coarse index with Rji=1R_{ji}=1. By [14] and (31), the prolonged restricted error has entries

(PRe)i=Pij(Re)j=πi(Re)j(Rπ)j.(PRe)_i=P_{ij}(Re)_j=\pi_i\frac{(Re)_j}{(R\pi)_j}.

Substituting ei=πifie_i=\pi_i f_i and partitioning the sum over fine states by their coarse index jj gives

∥e−PRe∥π−12=∑i[ei−(PRe)i]2πi=∑j∑i:Rji=1πi[fi−(Re)j(Rπ)j]2,\|e-PRe\|_{\pi^{-1}}^2 = \sum_i\frac{[e_i-(PRe)_i]^2}{\pi_i} = \sum_j\sum_{i:R_{ji}=1}\pi_i\left[f_i-\frac{(Re)_j}{(R\pi)_j}\right]^2,

which proves (32). □

Proof of Proposition 4.3. Fix a coarse state Xc=Xc,(j)X^{c}=X^{c,(j)} at index jj with fine equivalence class Fj={i:Rji=1}\mathcal{F}_{j}=\{i:R_{ji}=1\} and conditional weights μj(i)=Pij=πi/(Rπ)j\mu_{j}(i)=P_{ij}=\pi_{i}/(R\pi)_{j}. If ∣Fj∣=1|\mathcal{F}_{j}|=1, both its conditional variance and internal Dirichlet energy vanish. Otherwise, temporarily label the Xh,scX^{c}_{h,s} molecules of each species ss in each aggregate ChC_{h} and let each labelled molecule diffuse independently on the connected subgraph ChC_{h} with reversible single-molecule generator Qh,sQ_{h,s} and stationary distribution ωv/Ωh\omega_{v}/\Omega_{h} (v∈Chv\in C_{h}). On the product space F~j=∏h,sChXh,sc\widetilde{\mathcal{F}}_{j}=\prod_{h,s}C_{h}^{X^{c}_{h,s}} of labelled placements v=(vh,s,p)v=(v_{h,s,p}), the joint stationary measure and generator are

μ~j(v)=∏h,s∏p=1Xh,scωvh,s,pΩh,Q~j=∑h,s∑p=1Xh,scI⊗⋯⊗Qh,s(p)⊗⋯⊗I.\widetilde{\mu}_{j}(v)=\prod_{h,s}\prod_{p=1}^{X^{c}_{h,s}}\frac{\omega_{v_{h,s,p}}}{\Omega_{h}},\qquad\widetilde{Q}_{j}=\sum_{h,s}\sum_{p=1}^{X^{c}_{h,s}}I\otimes\cdots\otimes Q_{h,s}^{(p)}\otimes\cdots\otimes I.

Because the eigenvalues of −Q~j-\widetilde{Q}_{j} are sums of the nonnegative eigenvalues of −Qh,s(p)-Q_{h,s}^{(p)}, the smallest positive eigenvalue of −Q~j-\widetilde{Q}_{j} is at least λ∗\lambda_{*}. The spectral expansion on L2(F~j,μ~j)L^{2}(\widetilde{\mathcal{F}}_{j},\widetilde{\mu}_{j}) therefore yields the Poincaré inequality

∑v∈F~jμ~j(v)[f~(v)−∑wμ~j(w)f~(w)]2≤12λ∗∑v≠wμ~j(v)(Q~j)w,v[f~(v)−f~(w)]2.\sum_{v\in\widetilde{\mathcal{F}}_{j}}\widetilde{\mu}_{j}(v)\left[\widetilde{f}(v)-\sum_{w}\widetilde{\mu}_{j}(w)\widetilde{f}(w)\right]^{2}\leq\frac{1}{2\lambda_{*}}\sum_{v\ne w}\widetilde{\mu}_{j}(v)(\widetilde{Q}_{j})_{w,v}\left[\widetilde{f}(v)-\widetilde{f}(w)\right]^{2}.

Evaluating this inequality on functions f~(v)=fi\widetilde{f}(v)=f_{i} that depend only on the unlabelled voxel counts X(i)X^{(i)}, sums μ~j(v)\widetilde{\mu}_{j}(v) over the ∏h,s(Xh,sc!/∏v∈ChXv,s(i)!)\prod_{h,s}(X^{c}_{h,s}!/\prod_{v\in C_{h}}X^{(i)}_{v,s}!) permutations in each count state i∈Fji\in\mathcal{F}_{j} to recover the multinomial weight μj(i)=Pij\mu_{j}(i)=P_{ij} and the count-space jump rates dv,w(s)Xv,s(i)=(Ad)mid^{(s)}_{v,w}X^{(i)}_{v,s}=(A_{\mathrm d})_{mi}. Consequently,

∑i∈Fjμj(i)[fi−(Re)j(Rπ)j]2≤12λ∗∑i,m∈Fji≠mμj(i)(Ad)mi(fi−fm)2.\sum_{i\in\mathcal{F}_{j}}\mu_{j}(i)\left[f_{i}-\frac{(R e)_{j}}{(R\pi)_{j}}\right]^{2}\leq\frac{1}{2\lambda_{*}}\sum_{\substack{i,m\in\mathcal{F}_{j}\\i\ne m}}\mu_{j}(i)(A_{\mathrm d})_{mi}(f_{i}-f_{m})^{2}.

Multiplying by (Rπ)j(R\pi)_{j} and summing over all coarse classes jj yields ∥e−PRe∥π−12≤λ∗−1Ein(f)\|e-PRe\|_{\pi^{-1}}^{2}\leq\lambda_{*}^{-1}E_{\mathrm{in}}(f) by (32).

Proof of Proposition 4.4. For α=max⁡i(−Aii)≥0\alpha=\max_{i}(-A_{ii})\geq0, the shifted matrix A+αIA+\alpha I has nonnegative entries, so etA=e−αtet(A+αI)e^{tA}=e^{-\alpha t}e^{t(A+\alpha I)} is entrywise nonnegative for all t≥0t\geq0. Since 1⊤A≤0\mathbf{1}^{\top}A\leq0, differentiating 1⊤etA\mathbf{1}^{\top}e^{tA} shows that the column sums of etAe^{tA} do not exceed one, giving ∥etA∥1≤1\|e^{tA}\|_{1}\leq1. For σ>0\sigma>0, the Laplace integral for the resolvent gives

Aσ−1=∫0∞e−σtetA dt,∥Aσ−1∥1≤∫0∞e−σt∥etA∥1 dt≤σ−1.A_{\sigma}^{-1}=\int_{0}^{\infty}e^{-\sigma t}e^{tA}\,dt,\qquad\|A_{\sigma}^{-1}\|_{1}\leq\int_{0}^{\infty}e^{-\sigma t}\|e^{tA}\|_{1}\,dt\leq\sigma^{-1}.

Applying this operator norm bound to x−Aσ−1b=−Aσ−1(b−Aσx)x-A_{\sigma}^{-1}b=-A_{\sigma}^{-1}(b-A_{\sigma}x) 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 (ω=1\omega= 1), subject to immigration ∅→S\varnothing\to\mathrm{S} with propensity 1 and degradation S→∅\mathrm{S} \to\varnothing with propensity XX. In this single-voxel CME, the states are the integer copy numbers X∈{0,1,2,…}X \in\{0, 1, 2, \ldots\}, and the probability vector has one component for each count. An immigration event transfers probability flux from component XX to component X+1X+1.

Partitioning the unit domain into two voxels of equal volume ω1=ω2=1/2\omega_1 = \omega_2 = 1/2 yields spatial configurations X=(X1,X2)\mathbf{X} = (X_1, X_2) with joint probabilities p(X1,X2,t)p(X_1, X_2, t). In each voxel v∈{1,2}v \in\{1, 2\}, immigration occurs at rate 1/21/2 and degradation occurs at rate XvX_v. Let d>0d > 0 denote the diffusive jump rate per molecule between the two voxels. An immigration event in voxel 1 transitions state (1,0)(1, 0) to (2,0)(2, 0) at rate 1/21/2, whereas a diffusive jump transitions (2,0)(2, 0) to (1,1)(1, 1) at rate 2d2d.

Truncating the state space by total population X1+X2≤Nmax⁡X_1+X_2 \le N_{\max} with cap Nmax⁡=2N_{\max} = 2 retains the six configurations

(0,0),(1,0),(0,1),(2,0),(1,1),(0,2).(34)(0,0),\quad(1,0),\quad(0,1),\quad(2,0),\quad(1,1),\quad(0,2). \tag*{(34)}

Ordering the probability vector according to (S1.1) groups states by total population k=0,1,2k=0,1,2. The configuration (2,2)(2,2) is excluded because the FSP cap bounds the total copy number X1+X2X_1+X_2 rather than each voxel count separately. Any immigration event occurring in the k=2k=2 block transitions to a state with k=3k=3 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 6×66 \times6 FSP generator

A=(−1110001/2−2−dd2101/2d−2−d01201/20−3−2dd001/21/22d−3−2d2d001/20d−3−2d)(35)\mathbf{A} = \begin{pmatrix} -1 & 1 & 1 & 0 & 0 & 0 \\ 1/2 & -2-d & d & 2 & 1 & 0 \\ 1/2 & d & -2-d & 0 & 1 & 2 \\ 0 & 1/2 & 0 & -3-2d & d & 0 \\ 0 & 1/2 & 1/2 & 2d & -3-2d & 2d \\ 0 & 0 & 1/2 & 0 & d & -3-2d \end{pmatrix} \tag*{(35)}

The first three columns correspond to states with X1+X2<2X_1 + X_2 < 2 and have column sums equal to zero, whereas the last three columns correspond to X1+X2=2X_1 + X_2 = 2 and have column sums equal to −1-1 due to the absorbed immigration flux. Increasing the cap from Nmax⁡=2N_{\max} = 2 to Nmax⁡=3N_{\max} = 3 appends the four states (3,0),(2,1),(1,2),(0,3)(3, 0),(2, 1),(1, 2),(0, 3), 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 Ω1=ω1+ω2=1\Omega_1 = \omega_1 + \omega_2 = 1 gives the coarse count Xc=X1+X2∈{0,1,2}X^{c} = X_1 + X_2 \in\{0,1,2\}. The restriction operator RR sums entries over fine configurations with the same total XcX^{c}, while the prolongation operator PP distributes each molecule independently into voxel 1 or voxel 2 with equal probability ωv/Ω1=1/2\omega_v/\Omega_1 = 1/2. In the state ordering (S1.1), these operators take the block-diagonal form

R=(100000011000000111),P=(10001/2001/20001/4001/2001/4)(36)R = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}, \qquad P = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1/2 & 0 \\ 0 & 1/2 & 0 \\ 0 & 0 & 1/4 \\ 0 & 0 & 1/2 \\ 0 & 0 & 1/4 \end{pmatrix} \tag*{(36)}

In the solver implementation, the nonzeros of RR and PP are stored in the two length-6 arrays

parent=(0,1,1,2,2,2),weight=(1,1/2,1/2,1/4,1/2,1/4),\mathit{parent} = (0,1,1,2,2,2), \qquad\mathit{weight} = (1,1/2,1/2,1/4,1/2,1/4),

using zero-based coarse indices. For an example fine probability vector, restriction sums within each population block according to

XcX^{c}fine statesfine probabilitiespc(Xc)p_c(X^{c})
0(0, 0)0.100.10
1(1, 0), (0, 1)0.10, 0.100.20
2(2, 0), (1, 1), (0, 2)0.14, 0.35, 0.210.70

Table S1.4.

Applying the projection PRPR to this probability vector gives

p=(0.10,0.10,0.10,0.14,0.35,0.21)T,p = (0.10, 0.10, 0.10, 0.14, 0.35, 0.21)^{\mathsf{T}},
PRp=(0.10,0.10,0.10,0.175,0.35,0.175)T.PRp = (0.10, 0.10, 0.10, 0.175, 0.35, 0.175)^{\mathsf{T}}.

The projected vector PRpPRp preserves the coarse marginal RpRp while replacing the asymmetric entries on the k=2k = 2 block by the binomial values 0.70×(1/4,1/2,1/4)T0.70 \times(1/4, 1/2, 1/4)^{\mathsf{T}}. Although RP=IRP = I ensures that restricting a prolonged vector recovers the coarse vector, PRPR has rank three and cannot recover the fine components in the null space of RR.

This two-voxel system can itself serve as an intermediate level in a deeper hierarchy. Starting from a chain of four voxels at cap Nmax⁡=2N_{\max}=2 (15 states), pairing voxels {1,2}\{1,2\} and {3,4}\{3,4\} maps a fine state such as (1,0,0,1)(1,0,0,1) to the two-voxel state (1,1)(1,1) and then to the single-voxel CME state 2, reducing the state-space dimension through 15→6→315 \to6 \to3 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 3×33 \times3 coarse generator

Ac=RAP=(−1101−2201−3).(37)A_c=RAP=\begin{pmatrix}-1&1&0\\1&-2&2\\0&1&-3\end{pmatrix}. \tag*{(37)}

All diffusive parameter dd terms cancel identically in RAPRAP because diffusive jumps remain within the single aggregate {1,2}\{1,2\}. The coarse immigration rates sum to 1/2+1/2=11/2+1/2=1, the coarse degradation rates sum to X1+X2=XcX_1+X_2=X^c, and the third column retains its column sum of −1-1 from the absorbed immigration channel at Xc=2X^c=2. Thus AcA_c 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 hh and fine jump rate D/h2D/h^2, 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 ωv/Ωk=1/2\omega_v/\Omega_k=1/2, the Galerkin coarse jump rate (21) between the two aggregates is dc=(1/2)(D/h2)=D/(2h2)d^c=(1/2)(D/h^2)=D/(2h^2). By contrast, naive finite-difference rediscretization at coarse mesh spacing 2h2h with diffusivity DD would assign jump rate D/(2h)2=D/(4h2)D/(2h)^2=D/(4h^2), differing by a factor of two from the Galerkin rate RAPRAP.

A Coarse Correction

To trace a single coarse-grid correction step, consider backward Euler with step size Δt=1\Delta t=1 (σ=1\sigma=1) starting from the empty state b=p(0)=(1,0,0,0,0,0)Tb=p(0)=(1,0,0,0,0,0)^\mathsf{T}. Initializing the solve with x=bx=b for Aσ=I−AA_\sigma=I-A gives the fine residual and its restriction

r=b−Aσx=(−1,1/2,1/2,0,0,0)T,Rr=(−1,1,0)T.r=b-A_\sigma x=(-1,1/2,1/2,0,0,0)^\mathsf{T},\qquad Rr=(-1,1,0)^\mathsf{T}.

Solving the shifted coarse equation (I−Ac)ec=Rr(I-A_c)e_c=Rr yields

(2−10−13−20−14)ec=(−110),ec=(−3/81/161/16).\begin{pmatrix}2&-1&0\\-1&3&-2\\0&-1&4\end{pmatrix}e_c= \begin{pmatrix}-1\\1\\0\end{pmatrix},\qquad e_c=\begin{pmatrix}-3/8\\1/16\\1/16\end{pmatrix}.

Prolonging ece_c by PP and adding the correction to xx produces the updated fine iterate

x+=x+Pec=(5/8,1/8,1/8,1/64,1/32,1/64)T.x^+=x+Pe_c=(5/8,1/8,1/8,1/64,1/32,1/64)^\mathsf{T}.

Direct multiplication verifies that (I−A)x+=b(I-A)x^+=b for every d>0d>0, with retained probability mass 1Tx+=15/16\mathbf{1}^\mathsf{T}x^+=15/16. 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 PP 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 PP. Suppose we add the bimolecular birth reaction 2S→3S2S \to3S with rate constant c>0c > 0 in each voxel of volume 1/21/2. Its combined propensity across the two voxels is

2c[(X12)+(X22)],2c\left[\binom{X_1}{2}+\binom{X_2}{2}\right],

which evaluates to 2c2c, 00, and 2c2c on the three states (2,0)(2,0), (1,1)(1,1), and (0,2)(0,2) of the k=2k=2 block. Averaging these three values with the binomial prolongation weights (1/4,1/2,1/4)T(1/4,1/2,1/4)^{\mathsf{T}} gives the coarse propensity c(Xc2)=cc\binom{X_c}{2}=c at Xc=2X^c=2, in agreement with Theorem 4.1. The true outgoing flux from the k=2k=2 block, however, depends on how much probability resides in (1,1)(1,1) versus (2,0)(2,0) and (0,2)(0,2), so the coarse counts do not evolve autonomously and the solver must iterate on the fine system.

On the k=2k=2 block, an error subvector proportional to the binomial weights (1,2,1)T(1,2,1)^{\mathsf{T}} lies in the range of PP and is reproduced exactly by PRPR, whereas an oscillatory error subvector (1,−2,1)T(1,-2,1)^{\mathsf{T}} lies in the null space of RR and is omitted by PRPR. Proposition 4.3 bounds this omitted component in terms of the Dirichlet energy of diffusive jumps between the two voxels, while relaxation sweeps on AσA_\sigma damp (1,−2,1)T(1,-2,1)^{\mathsf{T}} 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 bcb_c be the restricted residual from § 1.3.6 and let Aσ,c=Aσ,l+1A_{\sigma,c}=A_{\sigma,l+1}. A zero right-hand side returns zero, and a direction with zero image under Aσ,cA_{\sigma,c} 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

v1=Cycle⁡(l+1,bc),α1=(Aσ,cv1)Tbc∥Aσ,cv1∥22,r1=bc−α1Aσ,cv1.(38)v_1=\operatorname{Cycle}(l+1,b_c),\qquad \alpha_1=\frac{(A_{\sigma,c}v_1)^{\mathsf{T}}b_c}{\lVert A_{\sigma,c}v_1\rVert_2^2},\qquad r_1=b_c-\alpha_1 A_{\sigma,c}v_1. \tag*{(38)}

When ∥r1∥2≤∥bc∥2/4\lVert r_1\rVert_2\leq\lVert b_c\rVert_2/4, the correction ec=α1v1e_c=\alpha_1v_1 is accepted. Otherwise, we compute a second recursive direction from r1r_1 and subtract its component along the first so that their images under Aσ,cA_{\sigma,c} are orthogonal,

v2=Cycle⁡(l+1,r1),β=(Aσ,cv1)TAσ,cv2∥Aσ,cv1∥22,v2′=v2−βv1,α2=(Aσ,cv2′)Tr1∥Aσ,cv2′∥22,ec=α1v1+α2v2′.(39)\begin{aligned} v_2&=\operatorname{Cycle}(l+1,r_1),\qquad \beta=\frac{(A_{\sigma,c}v_1)^{\mathsf{T}}A_{\sigma,c}v_2}{\lVert A_{\sigma,c}v_1\rVert_2^2},\qquad v'_2=v_2-\beta v_1,\\ \alpha_2&=\frac{(A_{\sigma,c}v'_2)^{\mathsf{T}}r_1}{\lVert A_{\sigma,c}v'_2\rVert_2^2},\qquad e_c=\alpha_1v_1+\alpha_2v'_2. \tag*{(39)} \end{aligned}

The orthogonality relations (Aσ,cv1)TAσ,cv2′=0(A_{\sigma,c}v_1)^{\mathsf{T}}A_{\sigma,c}v'_2=0 and (Aσ,cv1)Tr1=0(A_{\sigma,c}v_1)^{\mathsf{T}}r_1=0 imply that these coefficients minimize ∥bc−Aσ,cec∥2\lVert b_c-A_{\sigma,c}e_c\rVert_2 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 bcb_c 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 PRePRe and the Galerkin coarse correction both lie in the range of PP, but their coefficients are determined differently. Whereas PRePRe uses restriction alone, the coarse correction solves the Galerkin system for the restricted residual. For Aσ=σI−AA_{\sigma}=\sigma I-A with σ>0\sigma>0, an exact coarse solve maps an error ee to CeCe, where

C=I−PAσ,c−1RAσ,Aσ,c=RAσP.C=I-PA_{\sigma,c}^{-1}RA_{\sigma},\qquad A_{\sigma,c}=RA_{\sigma}P.

The identities C2=CC^{2}=C, CP=0CP=0, and RAσC=0RA_{\sigma}C=0 show that an exact coarse correction removes any error component in the range of PP and leaves zero restricted residual. Under detailed balance, the standard Galerkin argument [28] shows that this correction minimizes a weighted operator energy norm.

Let π\pi be positive weights on the retained fine states, with Π=diag⁡(π)\Pi=\operatorname{diag}(\pi) and Πc=diag⁡(Rπ)\Pi_{c}=\operatorname{diag}(R\pi), and retain fi=ei/πif_i=e_i/\pi_i. For example, linear immigration at rate ηωv\eta\omega_v and degradation at rate μXv\mu X_v (η,μ>0\eta,\mu>0) under reversible diffusion admit independent Poisson weights with means ηωv/μ\eta\omega_v/\mu [4], whose conditional distribution on the aggregate counts equals the prolongation weights PP.

Assume that Ajiπi=AijπjA_{ji}\pi_i=A_{ij}\pi_j holds for the complete retained generator and that πi/(Rπ)j=Pij\pi_i/(R\pi)_j=P_{ij} whenever Rji=1R_{ji}=1. The weighted operator H=Π−1AσH=\Pi^{-1}A_{\sigma} is then symmetric and satisfies

Πc−1R=PTΠ−1,Πc−1Aσ,c=PTHP.(40)\Pi_c^{-1}R=P^{\mathsf{T}}\Pi^{-1},\qquad\Pi_c^{-1}A_{\sigma,c}=P^{\mathsf{T}}HP. \tag*{(40)}

Since the absorbing loss rate from state X(i)X^{(i)} to omitted states is −∑jAji≥0-\sum_j A_{ji}\geq0, the quadratic form of HH in terms of the relative error ff is

eTHe=σ∑iπifi2+12∑i≠jπiAji(fj−fi)2+∑iπi(−∑jAji)fi2>0(e≠0).\begin{aligned} e^{\mathsf{T}}He={}&\sigma\sum_i\pi_i f_i^2+\frac{1}{2}\sum_{i\ne j}\pi_iA_{ji}(f_j-f_i)^2\\ &+\sum_i\pi_i\left(-\sum_jA_{ji}\right)f_i^2>0\qquad(e\ne0). \end{aligned}

The shift, transitions between retained states, and absorbing losses each contribute nonnegative terms, so ∥e∥H2=eTHe\lVert e\rVert_H^2=e^{\mathsf{T}}He is an energy norm on X\mathcal{X}. If Ad,inA_{d,\mathrm{in}} retains only diffusive jumps inside aggregates, Proposition 4.3 gives

∥e−PRe∥π−12≤λ∗−1eTΠ−1(−Ad,in)e≤λ∗−1eTHe.\lVert e-PRe\rVert_{\pi^{-1}}^2\leq\lambda_*^{-1}e^{\mathsf{T}}\Pi^{-1}(-A_{d,\mathrm{in}})e\leq\lambda_*^{-1}e^{\mathsf{T}}He.

By (S2.3), the corrected error CeCe is orthogonal in the HH-norm to the range of PP, giving

PTHC=Πc−1RAσ(I−PAσ,c−1RAσ)=0,∥e∥H2=∥Ce∥H2+∥(I−C)e∥H2,P^{\mathsf{T}}HC=\Pi_c^{-1}RA_{\sigma}(I-PA_{\sigma,c}^{-1}RA_{\sigma})=0,\qquad\lVert e\rVert_H^2=\lVert Ce\rVert_H^2+\lVert(I-C)e\rVert_H^2,

and hence

∥Ce∥H=min⁡zc∥e−Pzc∥H.\lVert Ce\rVert_H=\min_{z_c}\lVert e-Pz_c\rVert_H.

An exact coarse solve therefore selects the prolonged correction that minimizes the remaining error in the HH-norm.

The point Gauss–Seidel smoother of § 1.3.5 also reduces this norm. For the error ee before updating component ii and e+e^+ afterward, (He)i/Hii=(Aσe)i/(Aσ)ii(He)_i/H_{ii}=(A_{\sigma}e)_i/(A_{\sigma})_{ii} gives

ei+=ei−(He)iHii,ej+=ej(j≠i),∥e+∥H2=∥e∥H2−(He)i2Hii.e_i^+=e_i-\frac{(He)_i}{H_{ii}},\qquad e_j^+=e_j\quad(j\ne i),\qquad\lVert e^+\rVert_H^2=\lVert e\rVert_H^2-\frac{(He)_i^2}{H_{ii}}.

Equality over a full sweep requires every update to vanish, implying He=0H e = 0 and e=0e = 0. 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 FlF_l and BlB_l denote the error propagators of forward and reverse relaxation on level ll, and let ElE_l denote the error propagator of the complete cycle. The direct bottom solve gives EN1=0E_{N_1} = 0, while the V- and W-cycles satisfy

El=Bl[I−Pl(I−El+1γ)Aσ,l+1−1RlAσ,l]Fl,γ=1 or 2,E_l = B_l \left[I - P_l\left(I - E_{l+1}^{\gamma}\right)A_{\sigma,l+1}^{-1}R_lA_{\sigma,l}\right]F_l,\qquad\gamma= 1\text{ or }2,

with γ=1\gamma= 1 for V and γ=2\gamma= 2 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 HH-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 NvN_v voxels at cap Nmax⁡≥1N_{\max} \ge1, and let E\mathcal{E} 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

nnz⁡(Aσ)=(Nv+Nmax⁡Nmax⁡)+(2Nv+2∣E∣)(Nv+Nmax⁡−1Nmax⁡−1).\operatorname{nnz}(A_\sigma) = \binom{N_v + N_{\max}}{N_{\max}} + (2N_v + 2|\mathcal{E}|)\binom{N_v + N_{\max} - 1}{N_{\max} - 1}.

For each voxel, (Nv+Nmax⁡−1Nmax⁡−1)\binom{N_v + N_{\max} - 1}{N_{\max} - 1} states contain at least one molecule there and the same number lie below the cap and permit a birth. On a dd-dimensional Cartesian grid with 2∣E∣≤2dNv2|\mathcal{E}| \le2dN_v, this yields

nnz⁡(Aσ)≤[1+(2+2d)Nmax⁡](Nv+Nmax⁡Nmax⁡).\operatorname{nnz}(A_\sigma) \le\left[1 + (2 + 2d)N_{\max}\right]\binom{N_v + N_{\max}}{N_{\max}}.

For fixed Nmax⁡N_{\max}, the state count is asymptotic to NvNmax⁡/Nmax⁡!N_v^{N_{\max}}/N_{\max}!, so coarsening by 2d2^d voxels reduces the leading term by 2−dNmax⁡l2^{-dN_{\max}l} on level ll. With at most 2l2^l visits per W-cycle, the total work is bounded by a geometric sum of ratio 21−dNmax⁡2^{1-dN_{\max}}, which is O(N)O(N) independently of the number of levels when dNmax⁡>1dN_{\max} > 1 and O(Nlog⁡N)O(N\log N) when d=Nmax⁡=1d = N_{\max} = 1. 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 6.45×10−136.45 \times10^{-13} in ℓ1\ell_1. Relative to this reference at T=100T = 100, the Crank–Nicolson integrator with backward Euler startup has ℓ1\ell_1 errors 2.38×10−32.38 \times10^{-3}, 4.13×10−44.13 \times10^{-4}, 1.40×10−41.40 \times10^{-4}, and 2.26×10−52.26 \times10^{-5} at Δt=10\Delta t = 10, 5, 2.5, and 1.25, respectively.

Adaptive Population Selection

The adaptive FSP algorithm selects the population cap from a cumulative ℓ1\ell_1 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 (I−ΔtA)−1(I-\Delta t A)^{-1} is contractive in the ℓ1\ell_1 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 1−1Txm1-\mathbf{1}^{\mathsf{T}}x^m 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 tm/Tt_m/T. 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 xmx^m. 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 Nmax⁡N_{\max} to max⁡{Nmax⁡+4,⌈1.25(Nmax⁡+1)⌉}\max\{N_{\max}+4,\lceil1.25(N_{\max}+1)\rceil\} across all levels of the spatial hierarchy and repeats the step from the saved distribution xm−1x^{m-1}, padding the newly added population blocks with zeros without renormalizing previously absorbed mass. All existing diagonal blocks (Aσ,l)kk(A_{\sigma,l})_{kk} and their ILU(0) factors are retained without recomputation, along with the existing transfer entries. This procedure guarantees that the accepted discrete trajectory satisfies ∥p∗m−xm∥1≤εFSP(tm/T)\lVert p_*^m-x^m\rVert_1\leq\varepsilon_{\mathrm{FSP}}(t_m/T) at every step, while temporal discretization error relative to the continuous-time RDME is controlled through Δt\Delta t.

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 T=500T=500. Every linear solve converges to the prescribed tolerance (10−1310^{-13} at cap 56 and 10−1410^{-14} 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Δt\Delta tstatesP(k≥16)\mathbb{P}(k\geq16)P(k=20)\mathbb{P}(k=20)time (s)
5610487,6351.7719×10−61.7719\times10^{-6}1.2308×10−71.2308\times10^{-7}37.4
645814,3851.7746×10−61.7746\times10^{-6}1.2325×10−71.2325\times10^{-7}134.4
642.5814,3851.7746×10−61.7746\times10^{-6}1.2325×10−71.2325\times10^{-7}231.3
7251,282,9751.7746×10−61.7746\times10^{-6}1.2325×10−71.2325\times10^{-7}209.3

Table S1. Discretization refinement for the rare-switching RDME on four voxels at T=500T=500. All runs use the 4→2→14\to2\to1 W-cycle with one forward and one reverse ILU(0) block sweep per level, with solve tolerance 10−1310^{-13} at cap 56 and 10−1410^{-14} 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 ±1\pm1. 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 (Aσ,l)kk(A_{\sigma,l})_{kk}, an off-diagonal entry (i,j)(i,j) is modified by elimination of a prior pivot mm only if (i,m)(i,m), (m,j)(m,j), and (i,j)(i,j) 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 (Aσ,l)kk(A_{\sigma,l})_{kk}, 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 (Aσ,l)kk(A_{\sigma,l})_{kk}, 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 4→2→14 \to2 \to1 hierarchy (135,751 →\to 861 →\to 41 states) and plot all nonzero locations in Supplementary Figure S1. In the solver’s native ordering, states are sorted first by total population k=0,…,40k = 0, \ldots, 40 and then lexicographically by voxel counts. Because RlR_l and PlP_l conserve total population, both matrices are block diagonal across the 41 population blocks, and the sparsity pattern of RlR_l is the exact transpose of that of PlP_l.

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 4→24 \to2 transfers (135,751 nonzeros each), and panels (c,d) display the 2→12 \to1 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 (k+33)\binom{k+3}{3} on four voxels.

Supplementary Figure S2 zooms into the single population block k=4k = 4 of the 4→24 \to2 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 (X1cX_1^c, X2cX_2^c) 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 k=4k = 4 population block (35 fine states and 5 coarse states) of the 4→24 \to2 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 5×355 \times35 and prolongation has dimension 35×535 \times5, 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 NvN_v voxels of equal volume with spatially uniform rates, reversing the voxel index map v↦Nv+1−vv \mapsto N_v + 1 - v commutes with the FSP generator A\mathbf{A} (and similarly along each coordinate axis on a dd-dimensional Cartesian grid). Consequently, any configuration XX and its reflection X~\widetilde{X} carry identical probability p(X,t)=p(X~,t)p(X,t) = p(\widetilde{X},t) at all times t≥0t \ge0. Storing the combined probability p(X,t)+p(X~,t)p(X,t) + p(\widetilde{X},t) as a single unknown for each asymmetric pair {X,X~}\{X,\widetilde{X}\} and storing symmetric configurations (X=X~X = \widetilde{X}) 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 XX into each destination group gives the exact reduced generator with the same absorbing boundary losses. Because uniform 2d2^d 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 4→2→14 \to2 \to1 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 4.76×10−164.76 \times10^{-16} in the ℓ1\ell_1 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 (2,2,2,2)(2,2,2,2) to T=20T = 20 using backward Euler with Δt=2\Delta t = 2, cumulative FSP error budget εFSP=10−5\varepsilon_{\mathrm{FSP}} = 10^{-5}, and linear solve tolerance ε=10−10\varepsilon= 10^{-10} under the acceptance rule of Section S3.2. Both implementations dynamically expand the population cap from Nmax⁡=8N_{\max} = 8 to Nmax⁡=82N_{\max} = 82 through identical step rejections and execute 666 total W-cycles.

ProblemStored unknowns baselineStored unknowns reducedTime (s) baselineTime (s) reducedMemory (GiB) baselineMemory (GiB) reduced
Rare switching487,635244,03536.7118.370.1990.084
Adaptive Schlögl2,123,5551,062,22960.0330.500.9030.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 9.06×10−159.06 \times10^{-15} and 3.95×10−143.95 \times10^{-14} in the ℓ1\ell_1 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 1.29×10−151.29 \times10^{-15} in ℓ1\ell_1. 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 k=∑vXvk = \sum_v X_v, 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 ωv=20\omega_v = 20 and unit spacing, with diffusive jump rate 1 per molecule to each adjacent voxel. The local Schlögl reaction constants are chosen as (c1,c2,c3,c4)=(0.17,0.03,0.5,0.4)(c_1, c_2, c_3, c_4) = (0.17, 0.03, 0.5, 0.4), corresponding to a deterministic reaction drift −0.005(u−2)(u−5)(u−10)-0.005(u-2)(u-5)(u-10) for concentration u=Xv/ωvu = X_v/\omega_v with stable equilibria at u=2u = 2 (Xv=40X_v = 40) and u=10u = 10 (Xv=200X_v = 200) separated by an unstable barrier at u=5u = 5 (Xv=100X_v = 100). 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 T=300T = 300, recording voxel counts every 2 time units.

Figure S3 plots the empirical probability P(Xv/20≥5,t)\mathbb{P}(X_v/20 \ge5,t) that a voxel has concentration at least 5 as the stochastic front advances from voxel 16. At T=300T = 300, 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 P(Xv/20≥5)\mathbb{P}(X_v/20 \ge5) 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 P(Xv/20≥5,t)P(X_v/20 \ge5, t). Surrounding histograms A–D show the normalized count distributions in individual voxels at t=300t = 300 (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. [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. [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. [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. [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. [5]A. Brandt, Multi-level adaptive solutions to boundary-value problems, Mathematics of Computation, 31 (1977), pp. 333–390.
  6. [6]F. R. K. Chung, Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, vol. 92, American Mathematical Society, Providence, RI, 1997.
  7. [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. [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. [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. [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. [11]D. T. Gillespie, Exact stochastic simulation of coupled chemical reactions, The Journal of Physical Chemistry, 81 (1977), pp. 2340–2361.DOI
  12. [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. [13]M. Hegland, Approximating the solution of the chemical master equation by aggregation, ANZIAM Journal, 50 (2008), pp. C371–C384.
  14. [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. [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. [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. [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. [18]J. G. Kemeny and J. L. Snell, Finite Markov Chains, Springer-Verlag, New York, 1976.
  19. [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. [20]Y. Notay and P. S. Vassilevski, Recursive Krylov-based multigrid cycles, Numerical Linear Algebra with Applications, 15 (2008), pp. 473–487.DOI
  21. [21]Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, 2003.DOI
  22. [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. [23]R. I. Saye, Cascading smoothers for multigrid, preprint, arXiv:2606.12577, 2026, https://arxiv.org/abs/2606.12577.
  24. [24]F. Schlögl, Chemical reaction models for non-equilibrium phase transitions, Zeitschrift für Physik, 253 (1972), pp. 147–161.
  25. [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. [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. [27]U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid, Academic Press, London, 2001.
  28. [28]J. Xu, Iterative methods by space decomposition and subspace correction, SIAM Review, 34 (1992), pp. 581–613.DOI

Paper details

vlnc:W_b8v93gmq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents