Equation-free modeling

From Wikipedia, the free encyclopedia

Equation-free modeling is a method for multiscale computation and computer-aided analysis. It is designed for a class of complicated systems in which one observes evolution at a macroscopic, coarse scale of interest, while accurate models are only given at a finely detailed, microscopic, level of description. The framework empowers one to perform macroscopic computational tasks (over large space-time scales) using only appropriately initialized microscopic simulation on short time and small length scales. The methodology eliminates the derivation of explicit macroscopic evolution equations when these equations conceptually exist but are not available in closed form; hence the term equation-free.^[1]

Introduction

In a wide range of chemical, physical and biological systems, coherent macroscopic behavior emerges from interactions between microscopic entities themselves (molecules, cells, grains, animals in a population, agents) and with their environment. Sometimes, remarkably, a coarse-scale differential equation model (such as the Navier-Stokes equations for fluid flow, or a reaction-diffusion system) can accurately describe macroscopic behavior. Such macroscale modeling makes use of general principles of conservation (atoms, particles, mass, momentum, energy), and closed into a well-posed system through phenomenological constitutive equations or equations of state. However, one increasingly encounters complex systems that only have known microscopic, fine scale, models. In such cases, although we observe the emergence of coarse-scale, macroscopic behavior, modeling it through explicit closure relations may be impossible or impractical. Non-Newtonian fluid flow, chemotaxis, porous media transport, epidemiology, brain modeling and neuronal systems are some typical examples. Equation-free modeling aims to use such microscale models to predict coarse macroscale emergent phenomena.

Performing coarse-scale computational tasks directly with fine-scale models is often infeasible: direct simulation over the full space-time domain of interest is often computationally prohibitive. Moreover, modeling tasks, such as numerical bifurcation analysis, are often impossible to perform on the fine-scale model directly: a coarse-scale steady state may not imply a steady state for the fine-scale system, since individual molecules or particles do not stop moving when the gas density or pressure become stationary. Equation-free modeling circumvents such problems by using short bursts of appropriately initialized fine-scale simulation.^[2]

The coarse time-stepper

Dynamic problems invoke the coarse time-stepper. In essence, short bursts of computational experiments with the fine-scale simulator estimate local time derivatives. Given an initial condition for the coarse variables $U(t_{k})$ at time $t_{k}$ , the coarse time-stepper involves four steps:

Lifting, creates microscale initial conditions $u(t_{k})$ , consistent with the macrostate $U(t_{k})$ ;
Simulation, uses the microscale simulator to compute the microscale state $u(t)$ at over a short interval $t_{k}\leq t\leq t_{k}+\delta t$ ;
Restriction, obtains the macrostate $U(t_{k}+\delta t)$ from the fine-scale state $u(t)$ ;
the Time-step, extrapolation of macrostate $U$ from $t_{k}$ to $t_{{k+1}}=t_{k}+\Delta t$ predicts the state a macrotime in the future.

Multiple time steps simulates the system into the macro-future. If the microscale model is stochastic, then an ensemble of microscale simulations may be needed to obtain sufficiently good extrapolation in the time step. Such a coarse time-stepper may be used in many algorithms of traditional continuum numerical analysis, such as numerical bifurcation analysis, optimization, control, and even accelerated coarse-scale simulation.

Traditionally, algebraic formulae determine time derivatives of the coarse model. In our approach, the macroscale derivative is estimated by the inner microscale simulator, in effect performing a closure on demand. A reason for the name equation-free is by analogy with matrix-free numerical linear algebra;^[3] the name emphasizes that macro-level equations are never constructed explicitly in closed form.

Restriction

The restriction operator often follows directly from the specific choice of the macroscale variables. For example, when the microscale model evolves an ensemble of many particles, the restriction typically computes the first few moments of the particle distribution (the density, momentum, and energy).

Lifting

The lifting operator is usually much more involved. For example, consider a particle model: we need to define a mapping from a few low order moments of the particle distribution to initial conditions for each particle. The assumption that a relation exists that closes in these low order, coarse, moments, implies that the detailed microscale configurations are functionals of the moments (sometimes referred to as slaving ^[4]). We assume this relationship is established/emerges on time scales that are fast compared to the overall system evolution (see slow manifold theory and applications ^[5]). Unfortunately, the closure (slaving relations) are algebraically unknown (as otherwise the coarse evolution law would be known).

Initializing the unknown microscale modes randomly introduces a lifting error: we rely on the separation of macro and micro time scales to ensure a quick relaxation to functionals of the coarse macrostates (healing). A preparatory step may be required, possibly involving microscale simulations constrained to keep the macrostates fixed.^[6] When the system has a unique fixed point for the unknown microscale details conditioned upon the coarse macrostates, a constrained runs algorithm may perform this preparatory step using only the microscale time-stepper.^[7]

An illustrative example

A toy problem illustrates the basic concepts. For example, consider the differential equation system for two variables $(U(t),u(t))$ :

${\frac {dU}{dt}}=-U-u+2\,,\quad {\frac {du}{dt}}=100(U^{3}-u).$

Capital $U$ denotes the presumed macroscale variable, and lowercase $u$ the microscale variable. This classification means that we assume a coarse model of the form $dU/dt=G(U)$ exists, although we do not necessarily know what it is. Arbitrarily define the lifting from any given macrosate $U$ as $(U,u)=(U,0.5)$ . A simulation using this lifting and the coarse time-stepper is shown in the figure.

Equation-free coarse time-stepper applied to the illustrative example differential equation system using $\delta t=0.1$ and Failed to parse(lexing error): U(0)=−1.

The solution of the differential equation rapidly moves to the slow manifold $u\approx U^{3}$ for any initial data. The coarse time-stepper solution would agree better with the full solution when the 100 factor is increased. The graph shows the lifted solution (blue solid line) $(U,u)$ . At times $t=n\delta t$ , the solution is restricted and then lifted again, which here is simply setting $u(n\delta t)=0.5$ . The slow manifold is shown as a red line. The right plot shows the time derivative of the restricted solution as a function of time (blue curve), as well as the time derivative $dU/dt$ (the coarse time derivative), as observed from a full simulation (red curve).

On application to concrete multiscale problems

The equation-free approach has been applied to many examples. They examples illustrate the various ways to construct and assemble the algorithmic building blocks. Numerical analysis establishes the accuracy and efficiency of this approach. Additional numerical analysis on other methods of this type has also been done.^[8]

Applying the equation-free paradigm to a real problem requires considerable care, especially defining the lifting and restriction operators, and the appropriate outer solver.

The first challenge is to identify the macroscale observables. They need to be complete enough so that the unknown microscale variables can be reliably reconstructed (lifted). Physical arguments often the identify the macroscale observables. Almost always one invokes densities, but there are some surprisingly simple examples where correlation functions are essential macroscale variables.^[9] If not resorting to physical arguments, then modern data-mining or manifold learning techniques, such as Isomap or diffusion maps, may obtain the macroscale variables from microscale simulation.^[10]
There should be a clear separation between the time-scales of the macroscale observables and the time-scales of the remaining microscale modes quasi-equilibrate given any macrostate.
Knowing the macroscale observables might not be sufficient. One strategy to obtain such information is the baby-bathwater scheme which uses only appropriately initialized simulations.^[11]

Coarse bifurcation analysis

The recursive projection method^[12] enables the computation of bifurcation diagrams using legacy simulation code. It also empowers the coarse time-stepper to perform equation-free bifurcation computations. Consider the coarse time stepper in its effective form

${\vec U}^{{n+1}}={\vec S}({\vec U}^{n},\lambda ;\delta t),$

which includes explicit dependence upon one or more parameters $\lambda$ . Bifurcation analysis computes equilibria or periodic orbits, their stability and dependence upon parameter $\lambda$ .

Compute a coarse equilibrium as a fixed point of the coarse time stepper

${\vec U}-{\vec S}({\vec U},\lambda ;\delta t)={\vec 0}.$

In the equation-free context, the recursive projection method is the outer solver of this equation, and the coarse time-stepper enables this method to be performed using fine scale dynamics.

Additionally, for problems where the macroscale has continuous symmetries, one can use a template based approach ^[13] to compute coarse self-similiar or travelling wave solutions as fixed points of a coarse time-stepper that also encodes appropriate rescaling and/or shifting of space-time and/or solution. For example, self-similar diffusion solutions may be found as the probability density function of detailed molecular dynamics.^[14]

An alternative to the recursive projection method is to use Newton--Krylov methods.^[15]

Coarse projective integration

Patch dynamics

Lifting

Boundary conditions

Open problems and future directions

References

↑ Kevrekidis, I.G.; Samaey, G. (2009), "Equation-free multiscale computation: algorithms and applications", Annual Review in Physical Chemistry 60: 321–344, doi:10.1146/annurev.physchem.59.032607.093610
↑ Kevrekidis, I.G. et al. (2003), "Equation-free, coarse-grained multiscale computation: enabling microscopic simulators to perform system-level tasks", Comm. Math. Sciences 1 (4): 715–762, MR 2041455
↑ C. T. Kelley. Iterative Methods for linear and nonlinear equations, SIAM, Philadelphia, 1995.
↑ H. Haken. Slaving principle revisited. Physica D, 97:95--103, 1996.
↑ A. J. Roberts. Effectively model dynamics, deterministic and stochastic, across multiple space and time scales. In J. G. Hartnett and P. C. Abbott, editors, Frontiers of Fundamental and Computational Physics: 10th International Symposium, volume 1246, pages 75--87. AIP, 2010.
↑ J. P. Ryckaert, G. Ciccotti, and H. Berendsen. Numerical integration of the Cartesian equation of motion of a system with constraints: molecular dynamics of N-alkanes. J. Comp. Phys., 23:237, 1977.
↑ C. W. Gear, T. J. Kaper, I. G. Kevrekidis, and A. Zagaris. Projecting to a Slow Manifold: Singularly Perturbed Systems and Legacy Codes. SIAM Journal on Applied Dynamical Systems 4(3):711--732, 2005.
↑ W. E and B. Engquist (2003). The heterogeneous multiscale methods Comm. Math. Sciences 1(1):87--132.
↑ W. R. Young, A. J. Roberts, and G. Stuhne. Reproductive pair correlations and the clustering of organisms. Nature, 412:328--331, 2001.
↑ R. R. Coifman et al. (2005). Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps Proceedings of the National Academy of Sciences 102(21):7426--7431.
↑ J. Li, P. G. Kevrekidis, C. W. Gear and I. G. Kevrekidis (2003). Deciding the nature of the coarse equation through microscopic simulations: the baby-bathwater scheme SIAM Multiscale Modeling and Simulation 1(3):391--407.
↑ G.M. Schroff and H.B. Keller (1993). Stabilization of unstable procedures: the recursive projection method SIAM Journal on Numerical Analysis 30: 1099-1120.
↑ C. Rowley and J. Marsden (2000). Reconstruction equations and the Karhunen-Loeve expansion for systems with symmetry Physica D: Nonlinear Phenomena 142: 1-19.
↑ L. Chen, P. Debenedetti, C.W. Gear, and I.G. Kevrekidis (2004). From molecular dynamics to coarse self-similar solutions: a simple example using equation-free computation Journal of Non-Newtonian Fluid Mechanics 120: 215-223.
↑ C.T. Kelley (1995). Iterative Methods for linear and nonlinear equations SIAM, Philadelphia.

External links

Equation-free modeling at Scholarpedia, curated by Yannis Kevrekidis.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.