Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “discrete stochastic simulation”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 19 records

Effect of excluded volume on 2D discrete stochastic chemical kinetics

The stochastic simulation algorithm (SSA) is widely used in the discrete stochastic simulation of chemical kinetics. The propensity functions which play a central role in this algorithm have been derived under the point-molecule assumption, i.e., that the total volume of the molecules is negligible compared to the volume of the container. It has been shown analytically that for a one-dimensional system and the A + A reaction, when the point-molecule assumption is relaxed, the propensity function need only be adjusted by replacing the total volume of the system with the free volume of the system. In this paper we investigate via numerical simulations the impact of relaxing the point-molecule assumption in two dimensions. We find that the distribution of times to the first collision is close to exponential in most cases, so that the formalism of the propensity function is still applicable. In addition, we find that the area excluded by the molecules in two dimensions is usually higher than their close-packed area, requiring a larger correction to the propensity function than just the replacement of the total volume by the free volume.

97 MATHEMATICS AND COMPUTING↗

Hybrid stochastic simulation of reaction-diffusion systems with slow and fast dynamics

In this paper, we present a novel hybrid method to simulate discrete stochastic reaction-diffusion models arising in biochemical signaling pathways. We study moderately stiff systems, for which we can partition each reaction or diffusion channel into either a slow or fast subset, based on its propensity. Numerical approaches missing this distinction are often limited with respect to computational run time or approximation quality. We design an approximate scheme that remedies these pitfalls by using a new blending strategy of the well-established inhomogeneous stochastic simulation algorithm and the tau-leaping simulation method. The advantages of our hybrid simulation algorithm are demonstrated on three benchmarking systems, with special focus on approximation accuracy and efficiency.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Time dependent solution for acceleration of tau-leaping

The tau-leaping method is often effective for speeding up discrete stochastic simulation of chemically reacting systems. However, when fast reactions are involved, the speed-up for this method can be quite limited. One way to address this is to apply a stochastic quasi-steady state assumption. However we must be careful when using this assumption. If the fast subsystem cannot reach a steady distribution fast enough, the quasi-steady-state assumption will propagate error into the simulation. To avoid these errors, we propose to use the time dependent solution rather than the quasi-steady-state. Generally speaking, the time dependent solution is not easy to derive for an arbitrary network. However, for some common motifs we do have time dependent solutions. We derive the time dependent solutions for these motifs, and then show how they can be used with tau-leaping to achieve substantial speed-ups, including for a realistic model of blood coagulation. Although the method is complicated, we have automated it.

97 MATHEMATICS AND COMPUTING↗

The Role of Chromatin Density in Cell Population Heterogeneity during Stem Cell Differentiation

We incorporate three-dimensional (3D) conformation of chromosome (Hi-C) and single-cell RNA sequencing data together with discrete stochastic simulation, to explore the role of chromatin reorganization in determining gene expression heterogeneity during development. While previous research has emphasized the importance of chromatin architecture on activation and suppression of certain regulatory genes and gene networks, our study demonstrates how chromatin remodeling can dictate gene expression distribution by folding into distinct topological domains. We hypothesize that the local DNA density during differentiation accentuate transcriptional bursting due to the crowding effect of chromatin. This phenomenon yields a heterogeneous cell population, thereby increasing the potential of differentiation of the stem cells.

59 BASIC BIOLOGICAL SCIENCES↗

Final Technical Report "Multiscale Simulation Algorithms for Biochemical Systems"

Biochemical systems are inherently multiscale and stochastic. In microscopic systems formed by living cells, the small numbers of reactant molecules can result in dynamical behavior that is discrete and stochastic rather than continuous and deterministic. An analysis tool that respects these dynamical characteristics is the stochastic simulation algorithm (SSA, Gillespie, 1976), a numerical simulation procedure that is essentially exact for chemical systems that are spatially homogeneous or well stirred. Despite recent improvements, as a procedure that simulates every reaction event, the SSA is necessarily inefficient for most realistic problems. There are two main reasons for this, both arising from the multiscale nature of the underlying problem: (1) stiffness, i.e. the presence of multiple timescales, the fastest of which are stable; and (2) the need to include in the simulation both species that are present in relatively small quantities and should be modeled by a discrete stochastic process, and species that are present in larger quantities and are more efficiently modeled by a deterministic differential equation (or at some scale in between). This project has focused on the development of fast and adaptive algorithms, and the fun- damental theory upon which they must be based, for the multiscale simulation of biochemical systems. Areas addressed by this project include: (1) Theoretical and practical foundations for ac- celerated discrete stochastic simulation (tau-leaping); (2) Dealing with stiffness (fast reactions) in an efficient and well-justified manner in discrete stochastic simulation; (3) Development of adaptive multiscale algorithms for spatially homogeneous discrete stochastic simulation; (4) Development of high-performance SSA algorithms.

97 MATHEMATICS AND COMPUTING↗

Parallel discrete-event simulation of FCFS stochastic queueing networks

Physical systems are inherently parallel. Intuition suggests that simulations of these systems may be amenable to parallel execution. The parallel execution of a discrete-event simulation requires careful synchronization of processes in order to ensure the execution's correctness; this synchronization can degrade performance. Largely negative results were recently reported in a study which used a well-known synchronization method on queueing network simulations. Discussed here is a synchronization method (appointments), which has proven itself to be effective on simulations of FCFS queueing networks. The key concept behind appointments is the provision of lookahead. Lookahead is a prediction on a processor's future behavior, based on an analysis of the processor's simulation state. It is shown how lookahead can be computed for FCFS queueing network simulations, give performance data that demonstrates the method's effectiveness under moderate to heavy loads, and discuss performance tradeoffs between the quality of lookahead, and the cost of computing lookahead.

Nicol, David M.↗

Adaptive hybrid simulations for multiscale stochastic reaction networks

The probability distribution describing the state of a Stochastic Reaction Network (SRN) evolves according to the Chemical Master Equation (CME). It is common to estimate its solution using Monte Carlo methods such as the Stochastic Simulation Algorithm (SSA). In many cases, these simulations can take an impractical amount of computational time. Therefore, many methods have been developed that approximate sample paths of the underlying stochastic process and estimate the solution of the CME. A prominent class of these methods include hybrid methods that partition the set of species and the set of reactions into discrete and continuous subsets. Such a partition separates the dynamics into a discrete and a continuous part. Simulating such a stochastic process can be computationally much easier than simulating the exact discrete stochastic process with SSA. Moreover, the quasi-stationary assumption to approximate the dynamics of fast subnetworks can be applied for certain classes of networks. However, as the dynamics of a SRN evolves, these partitions may have to be adapted during the simulation. We develop a hybrid method that approximates the solution of a CME by automatically partitioning the reactions and species sets into discrete and continuous components and applying the quasi-stationary assumption on identifiable fast subnetworks. Our method does not require any user intervention and it adapts to exploit the changing timescale separation between reactions and/or changing magnitudes of copy-numbers of constituent species. We demonstrate the efficiency of the proposed method by considering examples from systems biology and showing that very good approximations to the exact probability distributions can be achieved in significantly less computational time. This is especially the case for systems with oscillatory dynamics, where the system dynamics change considerably throughout the time-period of interest.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Sensitivity Analysis in the Presence of Intrinsic Stochasticity for Discrete Fracture Network Simulations

Abstract Large‐scale discrete fracture network (DFN) simulators are standard fare for studies involving the sub‐surface transport of particles since direct observation of real world underground fracture networks is generally infeasible. While these simulators have successfully been used in several engineering applications, estimates of output quantities of interest (QoI) — such as breakthrough time of particles reaching the edge of the system — suffer from two distinct types of uncertainty. A run of a DFN simulator requires several parameters to be set that dictate the placement and size of fractures, the density of fractures, and the overall permeability of the system; uncertainty on the proper parameters will lead to uncertainty in the QoI, called epistemic uncertainty. Furthermore, since these input settings to DFN simulators control the stochastic processes which place fractures and govern flow, understanding how this randomness affects the QoI requires several runs of the simulator at distinct random seeds. The uncertainty in the QoI attributed to different realizations (i.e., different seeds) of the same random process (i.e., identical input parameters) leads to a second type of uncertainty, called aleatoric uncertainty. In this paper, we perform a Sensitivity Analysis, which directly attributes the uncertainty observed in the QoI to the epistemic uncertainty from each input parameter and to the aleatoric uncertainty. Beyond the specific takeaways on which input variables influence uncertainty in the QoI the most, a major contribution of this paper is the introduction of a statistically rigorous workflow for characterizing the uncertainty in DFN flow simulations that exhibit heteroskedasticity.

58 GEOSCIENCES↗

U.S. airport entry screening in response to pandemic influenza: Modeling and analysis

Background: A stochastic discrete event simulation model to assess the effectiveness of passenger screening for Pandemic Influenza (PI) at U.S. airport ports of entry was developed. Methods: International passengers arriving at 18 U.S. airports (AP) from Asia, Europe, South America, and Canada were assigned to one of three states: not infected, infected with PI, infected with other respiratory illness. Passengers passed through layered screening then exited the model. 80% screening effectiveness was assumed for symptomatic passengers; 6% asymptomatic passengers. Results: In the first 100 days of a global pandemic, U.S. AP screening would evaluate over 17M passengers with 800K secondary screenings. 11,570 PI infected passengers (majority asymptomatic) would enter the U.S. undetected from all 18 APs. Foreign airport departure screening significantly decreased the false negative (infected/undetected) passengers. U.S. attack rates: no screening (26.9% - 30.9%); screening (26.4% - 30.6%); however AP screening results in 800K to 1.8M less U.S. PI cases; 16K-35K less deaths (2% fatality rate). Antiviral medications for travel contact prophylaxis (10 contacts/ PI passenger) was high - 8.8M. False positives all 18 APs: 100-200/day. Conclusions: Foreign shore exit screening greatly reduces numbers of infected PI passengers. U.S. AP screening identifies 50% infected individuals; efficacy is limited by the asymptomatic PI infected. Screening will not significantly delay arrival of PI via international air transport, but reduce the number of US cases and deaths.

99 GENERAL AND MISCELLANEOUS↗

Code for Experiment in Publication “Sensitivity Analysis in the Presence of Intrinsic Stochasticity for Discrete Fracture Network Simulations”

Following the Open Research requirements for AGU journals, we must release the code used to perform the experiment described in our recent publication, posted at (https://arxiv.org/abs/2312.04722). This code fits a joint emulator to data from a Discrete Fracture Network (DFN) simulation, performed using the open-source software DFNworks (https://dfnworks.lanl.gov/). All code to be released implements existing methods; there are no novel algorithms nor any major innovations to existing software.

Murph, Alexander↗

Lazy Updating of hubs can enable more realistic models by speeding up stochastic simulations

To respect the nature of discrete parts in a system, stochastic simulation algorithms (SSAs) must update for each action (i) all part counts and (ii) each action's probability of occurring next and its timing. This makes it expensive to simulate biological networks with well-connected “hubs” such as ATP that affect many actions. Temperature and volume also affect many actions and may be changed significantly in small steps by the network itself during fever and cell growth, respectively. Such trends matter for evolutionary questions, as cell volume determines doubling times and fever may affect survival, both key traits for biological evolution. Yet simulations often ignore such trends and assume constant environments to avoid many costly probability updates. Such computational convenience precludes analyses of important aspects of evolution. Here we present “Lazy Updating,” an add-on for SSAs designed to reduce the cost of simulating hubs. When a hub changes, Lazy Updating postpones all probability updates for reactions depending on this hub, until a threshold is crossed. Speedup is substantial if most computing time is spent on such updates. We implemented Lazy Updating for the Sorting Direct Method and it is easily integrated into other SSAs such as Gillespie's Direct Method or the Next Reaction Method. Testing on several toy models and a cellular metabolism model showed >10× faster simulations for its use-cases—with a small loss of accuracy. Thus we see Lazy Updating as a valuable tool for some special but important simulation problems that are difficult to address efficiently otherwise.

97 MATHEMATICS AND COMPUTING↗

Discretization errors in molecular dynamics simulations with deterministic and stochastic thermostats

We investigate the influence of numerical discretization errors on computed averages in a molecular dynamics simulation of TIP4P liquid water at 300 K coupled to different deterministic (Nose-Hoover and Nose-Poincare) and stochastic (Langevin) thermostats. We propose a couple of simple practical approaches to estimating such errors and taking them into account when computing the averages. We show that it is possible to obtain accurate measurements of various system quantities using step sizes of up to 70% of the stability threshold of the integrator, which for the system of TIP4P liquid water at 300 K corresponds to the step size of about 7 fs.

97 MATHEMATICS AND COMPUTING↗

Spatial dependence of the growth of polycyclic aromatic compounds in an ethylene counterflow flame

The complex environments that characterize combustion systems can influence the distribution of gas-phase species, the relative importance of various growth mechanisms and the chemical and physical characteristics of the soot precursors generated. In order to provide molecular insights on the effect of combustion environments on the formation of gas-phase species, in this paper, we study the temporal and spatial dependence of soot precursors growth mechanisms in an ethylene/oxygen/argon counterflow diffusion flame. As computational tools of investigation, we included fluid dynamics simulations and stochastic discrete modeling. Results show the relative importance of various reaction pathways in flame, with the hydrogen-abstraction-acetylene-addition mechanism contributing to the formation of pure hydrocarbons near the stagnation plane, and oxygen chemistry prevailing near the maximum temperature region, where the concentration of atomic oxygen reaches its peak and phenols, ethers and furan-embedded species are formed. The computational results show excellent agreement with measurements obtained using aerosol mass spectrometry coupled with vacuum-ultraviolet photoionization. Knowledge acquired in this study can be used to predict the type of compounds formed in various locations of the flame and eventually provide insights on the environmental parameters that influence the growth of soot precursors. In addition, the results reported in this paper highlight the importance of modeling counterflow flames in two or three dimensions to capture the spatial dependence of growth mechanisms of soot precursors.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Simulating local measurements on a quantum many-body system with stochastic matrix product states

We demonstrate how to simulate both discrete and continuous stochastic evolutions of a quantum many-body system subject to measurements using matrix product states. A particular, but generally applicable, measurement model is analyzed and a simple representation in terms of matrix product operators is found. The technique is exemplified by numerical simulations of the antiferromagnetic Heisenberg spin-chain model subject to various instances of the measurement model. In particular, we focus on local measurements with small support and nonlocal measurements, which induce long-range correlations.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Simulation to assess the efficacy of US airport entry scrreening of passengers for pandemic influenza

We present our methodology and stochastic discrete-event simulation developed to model the screening of passengers for pandemic influenza at the US port-of-entry airports. Our model uniquely combines epidemiology modelling, evolving infected states and conditions of passengers over time, and operational considerations of screening in a single simulation. The simulation begins with international aircraft arrivals to the US. Passengers are then randomly assigned to one of three states -- not infected, infected with pandemic influenza and infected with other respiratory illness. Passengers then pass through various screening layers (i.e. pre-departure screening, en route screening, primary screening and secondary screening) and ultimately exit the system. We track the status of each passenger over time, with a special emphasis on false negatives (i.e. passengers infected with pandemic influenza, but are not identified as such) as these passengers pose a significant threat as they could unknowingly spread the pandemic influenza virus throughout our nation.

45 MILITARY TECHNOLOGY, WEAPONRY, AND NATIONAL DEF↗

Mesh-Based Entry Vehicle and Explosive Debris Re-Contact Probability Modeling

The risk to a crewed vehicle arising from potential re-contact with fragments from an explosive breakup of any jettisoned spacecraft segments during entry has long sought to be quantified. However, great difficulty lies in efficiently capturing the potential locations of each fragment and their collective threat to the vehicle. The method presented in this paper addresses this problem by using a stochastic approach that discretizes simulated debris pieces into volumetric cells, and then assesses strike probabilities accordingly. Combining spatial debris density and relative velocity between the debris and the entry vehicle, the strike probability can be calculated from the integral of the debris flux inside each cell over time. Using this technique it is possible to assess the risk to an entry vehicle along an entire trajectory as it separates from the jettisoned segment. By decoupling the fragment trajectories from that of the entry vehicle, multiple potential separation maneuvers can then be evaluated rapidly to provide an assessment of the best strategy to mitigate the re-contact risk.

McPherson, Mark A.↗

An adaptive multi-level simulation algorithm for stochastic biological systems

Discrete-state, continuous-time Markov models are widely used in the modeling of biochemical reaction networks. Their complexity often precludes analytic solution, and we rely on stochastic simulation algorithms (SSA) to estimate system statistics. The Gillespie algorithm is exact, but computationally costly as it simulates every single reaction. As such, approximate stochastic simulation algorithms such as the tau-leap algorithm are often used. Potentially computationally more efficient, the system statistics generated suffer from significant bias unless tau is relatively small, in which case the computational time can be comparable to that of the Gillespie algorithm. The multi-level method [Anderson and Higham, “Multi-level Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics,” SIAM Multiscale Model. Simul. 10(1), 146–179 (2012)] tackles this problem. A base estimator is computed using many (cheap) sample paths at low accuracy. The bias inherent in this estimator is then reduced using a number of corrections. Each correction term is estimated using a collection of paired sample paths where one path of each pair is generated at a higher accuracy compared to the other (and so more expensive). By sharing random variables between these paired paths, the variance of each correction estimator can be reduced. This renders the multi-level method very efficient as only a relatively small number of paired paths are required to calculate each correction term. In the original multi-level method, each sample path is simulated using the tau-leap algorithm with a fixed value of τ. This approach can result in poor performance when the reaction activity of a system changes substantially over the timescale of interest. By introducing a novel adaptive time-stepping approach where τ is chosen according to the stochastic behaviour of each sample path, we extend the applicability of the multi-level method to such cases. We demonstrate the efficiency of our method using a number of examples.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗