Equation-free modeling

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, and, in spatial problems, on small well-separated patches of space.[2] [3] A free Matlab/Octave toolbox empowers people to use these equation-free methods. [4]

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 ${\displaystyle U(t_{k})}$ at time ${\displaystyle t_{k}}$, the coarse time-stepper involves four steps:

• Lifting, creates microscale initial conditions ${\displaystyle u(t_{k})}$, consistent with the macrostate ${\displaystyle U(t_{k})}$;
• Simulation, uses the microscale simulator to compute the microscale state ${\displaystyle u(t)}$ at over a short interval ${\displaystyle t_{k}\leq t\leq t_{k}+\delta t}$;
• Restriction, obtains the macrostate ${\displaystyle U(t_{k}+\delta t)}$ from the fine-scale state ${\displaystyle u(t)}$;
• the Time-step, extrapolation of macrostate ${\displaystyle U}$ from ${\displaystyle t_{k}}$ to ${\displaystyle 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. For deterministic systems, the Matlab/Octave toolbox provides a user with higher-order accurate time-steppers:[4] a second- and fourth-order Runge--Kutta scheme, and a general interface scheme.

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;[5] the name emphasizes that macro-level equations are never constructed explicitly in closed form.

An illustrative example

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

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

Capital ${\displaystyle U}$ denotes the presumed macroscale variable, and lowercase ${\displaystyle u}$ the microscale variable. This classification means that we assume a coarse model of the form ${\displaystyle dU/dt=G(U)}$ exists, although we do not necessarily know what it is. Arbitrarily define the lifting from any given macrostate ${\displaystyle U}$ as ${\displaystyle (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 ${\displaystyle \delta t=0.1}$ and ${\displaystyle U(0)=-1}$.

The solution of the differential equation rapidly moves to the slow manifold ${\displaystyle 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) ${\displaystyle (U,u)}$. At times ${\displaystyle t=n\delta t}$, the solution is restricted and then lifted again, which here is simply setting ${\displaystyle 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 ${\displaystyle dU/dt}$ (the coarse time derivative), as observed from a full simulation (red curve).

The recursive projection method[14] 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

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

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

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

${\displaystyle {\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 [15] to compute coarse self-similar 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.[16]

An alternative to the recursive projection method is to use Newton—Krylov methods.[17]

The coarse time stepper accelerates simulation over large macroscale times. In the scheme described above, let the large macro-time-step ${\displaystyle \Delta t\gg \delta t}$, and be on the time scale of the slow coarse dynamics. Let the computed ${\displaystyle U^{n}\approx U(n\Delta t)}$ in terms of the coarse variable, and let the microscale simulation compute ${\displaystyle U^{n,k}\approx U(n\Delta t+k\delta t)}$ from a local time simulation with initial condition that the coarse variable ${\displaystyle U(n\Delta t)=U^{n}=U^{n,0}}$. Then we approximate ${\displaystyle U((n+1)\Delta t)}$ via extrapolating over a gap by

${\displaystyle U^{n+1}=U^{n,k}+(\Delta t-k\delta t)F({\vec {U}}^{n})}$

where, for example, simple linear extrapolation would be

${\displaystyle F({\vec {U}}^{n})=(U^{n,k}-U^{n,k-1})/\delta t}$

This scheme is the called coarse projective forward Euler, and is the simplest in the class.

The ${\displaystyle k}$ steps taken before the extrapolation reflect that we must allow the system to settle onto a quasi-equilibrium (from the microscale point of view), so that we can make a reliable extrapolation of the slow dynamics. Then the size of the projective integration step is limited by stability of the slow modes.[18]

Higher order versions of coarse projective integration can be formed, analogous to Adams–Bashforth or Runge–Kutta.[19] Higher order schemes for systems where the microscale noise is still apparent on the macroscale time step are more problematic.[20]

The spatial analogue of projective integration is the gap-tooth scheme. The idea of the gap-tooth scheme is to perform simulations of small patches of space, the teeth, separated by unsimulated space, the gaps. By appropriately coupling the small patches of simulations we create a large scale, coarse level, simulation of the spatially extended system. When the microscale simulator is computationally expensive the gap-tooth scheme empowers efficient large scale prediction. Furthermore, it does this without us ever having to identify an algebraic closure for a large scale model. [21][22][23] The Matlab/Octave toolbox provides support to users to implement simulations on an rectangular grid of patches in 1D or 2D space.[4]

The combination of the gap-tooth scheme with coarse projective integration is called patch dynamics.

Assumptions and choices about the macroscale evolution are crucial in the equation-free scheme. The key assumption is that the variables we choose for the macroscale coupling must effectively close on the chosen macroscale. If the chosen macroscale length is too small then more coarse scale variables may be needed: for example, in fluid dynamics we conventionally close the PDEs for density, momentum and energy; yet in high speed flow especially at lower densities we need to resolve modes of molecular vibration because they have not equilibrated on the time scales of the fluid flow. Qualitatively the same considerations apply to the equation-free approach.

For many systems appropriate coarse variables are more-or-less known by experience. However, in complex situations there is a need to automatically detect the appropriate coarse variables, and then use them in the macroscale evolution. This needs much more research utilizing techniques from data mining and manifold learning. In some problems it could be that as well as densities, the appropriate coarse variables also need to include spatial correlations, as in the so-called Brownian bugs.[26]

The macroscale may have to be treated as a stochastic system, but then the errors are likely to be much larger and the closures more uncertain.

• Yannis Kevrekidis (ed.). "Equation-free modeling". Scholarpedia.