View source for Bitruncated tesseractic honeycomb

'''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 equation]]s when these equations conceptually exist but are not available in closed form; hence the term equation-free.<ref>{{citation| last1=Kevrekidis |first1=I.G. |last2=Samaey |first2=G. |year=2009 |title=Equation-free multiscale computation: algorithms and applications |journal=Annual Review in Physical Chemistry |volume=60 |pages=321–344 |doi=10.1146/annurev.physchem.59.032607.093610 }}</ref>

==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.<ref>{{citation |author=Kevrekidis, I.G. et al. |year=2003 |title=Equation-free, coarse-grained multiscale computation: enabling microscopic simulators to perform system-level tasks |journal=Comm. Math. Sciences |volume=1 |issue=4 |pages=715–762 |mr=2041455 }}</ref>

==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 <math>U(t_k)</math> at time <math>t_k</math>, the coarse time-stepper involves four steps:

* Lifting, creates microscale initial conditions <math>u(t_k)</math>, consistent with the macrostate <math>U(t_k)</math>;
* Simulation, uses the microscale simulator to compute the microscale state <math>u(t)</math> at over a short interval <math>t_k\leq t \leq t_k+\delta t</math>;
* Restriction, obtains the macrostate <math>U(t_k+\delta t)</math> from the fine-scale state <math>u(t)</math>;
* the Time-step, extrapolation of macrostate <math>U</math> from <math>t_k</math> to <math>t_{k+1}=t_k+\Delta t</math> 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;<ref>C. T. Kelley. ''Iterative Methods for linear and nonlinear equations'', SIAM, Philadelphia, 1995.</ref> 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 <ref>H. Haken. Slaving principle revisited. ''Physica D'', 97:95--103, 1996.</ref>).  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 <ref>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.</ref>).  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.<ref>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.</ref> 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.<ref>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.</ref>

===An illustrative example===

A toy problem illustrates the basic concepts.  For example, consider the [[differential equation]] system for two variables <math>(U(t),u(t))</math>:
:<math>\frac{dU}{dt}=-U-u+2\,,\quad \frac{du}{dt}=100(U^3-u).</math>
Capital <math>U</math> denotes the presumed macroscale variable, and lowercase <math>u</math> the microscale variable. This classification means that we assume a coarse model of the form <math>dU/dt=G(U)</math> exists, although we do not necessarily know what it is.   Arbitrarily define the lifting from any given macrosate <math>U</math> as <math>(U,u)=(U,0.5)</math>. A simulation using this lifting and the coarse time-stepper is shown in the figure.
[[File:EquationFreeProjectiveIntegration.png|400px|thumb|Equation-free coarse time-stepper applied to the illustrative example differential equation system using <math>\delta t=0.1</math> and <math>U(0)=−1</math>.]]

The solution of the differential equation rapidly moves to the [[slow manifold]]  <math>u\approx U^3</math> 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) <math>(U,u)</math>. At times <math>t=n\delta t</math>, the solution is restricted and then lifted again, which here is simply setting <math>u(n\delta t)=0.5</math>. 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 <math>dU/dt</math> (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.<ref>W. E and B. Engquist (2003). The heterogeneous multiscale methods ''Comm. Math. Sciences'' 1(1):87--132.</ref>

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.<ref>W. R. Young, A. J. Roberts, and G. Stuhne. Reproductive pair correlations and the clustering of organisms. Nature, 412:328--331, 2001.</ref> 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.<ref>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.</ref>
* 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.<ref>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.</ref>

==Coarse bifurcation analysis==

The recursive projection method<ref>G.M. Schroff and H.B. Keller (1993). Stabilization of unstable procedures: the recursive projection method <em>SIAM Journal on Numerical Analysis</em> 30: 1099-1120.</ref> enables the computation of [[bifurcation diagram]]s 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
:<math>\vec U^{n+1}=\vec S(\vec U^n,\lambda; \delta t),</math>
which includes explicit dependence upon one or more parameters <math>\lambda</math>.  Bifurcation analysis computes [[List of types of equilibrium|equilibria]] or [[periodic orbit]]s, their stability and dependence upon parameter <math>\lambda</math>.

Compute a coarse equilibrium as a [[fixed point (mathematics)|fixed point]] of the coarse time stepper
:<math>\vec U-\vec S(\vec U,\lambda; \delta t)=\vec 0.</math>
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 <ref>C. Rowley and J. Marsden (2000). Reconstruction equations and the Karhunen-Loeve expansion for systems with symmetry <em>Physica D: Nonlinear Phenomena</em> 142: 1-19.</ref> 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]].<ref>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 <em>Journal of Non-Newtonian Fluid Mechanics</em> 120: 215-223.</ref>

An alternative to the recursive projection method is to use Newton--Krylov methods.<ref>C.T. Kelley (1995). <em>Iterative Methods for linear and nonlinear equations</em> SIAM, Philadelphia.</ref>

==Coarse projective integration==

{{Empty section|date=November 2013}}

==Patch dynamics==

===Lifting===

===Boundary conditions===

==Open problems and future directions==

{{Empty section|date=November 2013}}

==References==
{{Reflist}}

==External links==
*{{Scholarpedia | title=Equation-free modeling | urlname=Equation-free_modeling |curator=Yannis Kevrekidis }}

[[Category:Algorithms and data structures]]