Blog - Petri net programming (part 3) (changes)

Showing changes from revision #8 to #9:
Added | ~~Removed~~ | ~~Chan~~ged

This page is a blog article in progress, written by David Tanzer. To discuss this article while it’s being written, visit the Azimuth Forum. Please remember that blog articles need HTML, not Markdown.

*guest post by David Tanzer*</i>

Last time we looked at stochastic Petri nets, which use a random event model for the reactions. Individual entities are represented by tokens that flow through the network. When the token counts get large, we observed that they can be approximated by continuous quantities, which opens the door to the application of continuous mathematics to the analysis of network dynamics.

A key result of this approach is the “rate equation,” which gives a law of motion for the expected sizes of the populations. *Equilibrium* can then be obtained by solving for zero motion. The rate equations are applied in chemistry, where they give the rates of change of the concentrations of the various species in a reaction.

But before discussing the rate equation, here I will talk about the mathematical form of this law of motion, which consists of differential equations. This form is naturally associated with deterministic systems involving continuous magnitudes. This includes the equations of motion for the sine wave:

and the graceful ellipses that are traced out by the orbits of the planets around the sun:

This post provides some mathematical context to programmers who have not worked on scientific applications. My goal is to get as many of you on board as possible, before setting sail with Petri net programming.

Let’s first consider the major approaches to equations in general. We’ll illustrate with a Diophantine equation

$x^9 + y^9 + z^9 = 2$

where x, y and z are integer variables.

In the **theoretical approach** (aka “qualitative analysis”), we start with the meaning of the equation and then proceed to reason about its solutions. Here are some simple consequences of this equation. They can’t all be zero, can’t all be positive, can’t all be negative, can’t all be even, and can’t all be odd.

In the **formula-based approach**, we seek formulas to describe the solutions. Here is an example of a formula (which does not solve our equation):

$\{(x,y,z) | x = n^3, y = 2n - 4, z = 4 n | 1 \leq n \leq 5 \}$

Such formulas are nice to have, but the pursuit of them is diabolically difficult. In fact, for Diophantine equations, even the question of whether an arbitrarily chosen equation has any solutions whatsoever has been proven to be algorithmically undecidable.

Finally, in the **computational approach**, we seek algorithms to enumerate or numerically approximate the solutions to the equations.

Let’s apply the preceding classification to differential equations.

A *differential* equation is one that constrains the rates at which the variables are changing. This can include constraints on the rates at which the rates are changing (second-order equations), etc. The equation is *ordinary* if there is a single independent variable, such as time, otherwise it is *partial*.

Consider the equation stating that a variable increases at a rate equal to its current value. The bigger it gets, the faster it increases. Given a starting value, this determines a process — the solution to the equation — which here is exponential growth.

Let $X(t)$ be the value at time t, and let’s initialize it to 1 at time 0. So we have:

$X(0) = 1$

$X'(t) = X(t)$

These are first-order equations, because the derivative is applied at most once to any variable. They are linear equations, because the terms on each side of the equations are linear combinations of either individual variables or derivatives (in this case all of the coefficients are 1). Note also that a system of differential equations may in general have zero, one, or multiple solutions. This example belongs to a class of equations which are proven to have a unique solution for each initial condition.

You could imagine more complex systems of equations, involving multiple dependent variables, all still depending on time. That includes the rate equations for a Petri net, which have one dependent variable for each of the population sizes. The ideas for such systems are an extension of the ideas for a single-variable system. Then, a state of the system is a vector of values, with one component for each of the dependent variables. For first-order systems, such as the rate equations, where the derivatives appear on the left-hand sides, the equations determine, for each possible state of the system, a “direction” and rate of change for the state of the system.

Now here is a simple illustration of what I called the theoretical approach. Can $X(t)$ ever become negative? No, because it starts out positive at time 0, and in order to later become negative, it must be decreasing at a time $t_1$ when it is still positive. That is to say, $X(t_1) \gt 0$, and $X'(t_1) \lt 0$. But that contradicts the assumption $X'(t) = X(t)$. The general lesson here is that we don’t need a solution formula in order to make such inferences.

For the rate equations, the theoretical approach leads to substantial theorems about the existence and structure of equilibrium solutions.

It is natural to look for concise formulas to solve our equations, but the results of this overall quest are largely negative. The exponential differential equation cannot be solved by any formula that involves a finite combination of simple operations. So the solution function must be treated as a new primitive, and given a name, say $\exp(t)$. But even when we extend our language to include this new symbol, there are many differential equations that remain beyond the reach of finite formulas. So an endless collection of primitive functions is called for. (As standard practice, we always include $\exp(t)$, and its complex extensions to the trigonometric functions, as primitives in our toolbox.)

But the hard mathematical reality does not end here, because even when solution formulas do exist, finding them may call for an ace detective. Only for certain classes of differential equations, such as the linear ones, do we have systematic solution methods.

The picture changes, however, if we let the formulas to contain an infinite number of operations. Then the arithmetic operators give a far-reaching base for defining new functions. In fact, as you can verify, the power series

$X(t) = 1 + t + t^2/2! + t^3/3! + ...$

which we view as an “infinite polynomial” over the time parameter t, exactly satisfies our equations for exponential motion, $X(0) = 1$ and $X'(t) = X(t)$. This power series therefore *defines* $\exp(t)$. By the way, applying it to the input 1 produces a definition for the transcendental e:

$e = e^1 = \exp(1) = X(1) = 1 + 1 + 1/2 + 1/6 + 1/24 + 1/120 + ... \approx 2.71828$

Let’s leave aside our troubles with formulas, and consider the computational approach. For broad classes of differential equations, there are approximation algorithms that be successfully applied.

For starters, any power series that satisfies a differential equation may work for a simple approximation method. If a series is known to converge over some range of inputs, then one can approximate the value at those points by stopping the computation after a finite number of terms.

But the standard methods work directly with the equations, provided that they can be put into the right form. The simplest one is called Euler’s method. It works over a sampling grid of points separated by some small number $\epsilon$. Let’s take the case where we have a first-order equation in explicit form, which means that X’(t) = f(X(t)), for some function f.

We begin with the initial value $X(0)$. Applying f, we get X’(0) = f(X(0)). Then for the interval from 0 to $\epsilon$, we use a linear approximation for X(t), by assuming that the derivative remains constant at $X'(0)$. That gives $X(\epsilon) = X(0) + \epsilon \cdot X'(0)$. Next, $X'(\epsilon) = f(X(\epsilon))$, and $X(2 \epsilon) = X(\epsilon) + \epsilon \cdot X'(\epsilon)$, etc. Formally,

$X(0) = initial$

$X((n+1) \epsilon) = X(n \epsilon) + \epsilon f(X(n \epsilon))$

Applying this to our exponential equation, where $f(X(t)) = X(t)$, we get:

$X(0) = 1$

$X((n+1) \epsilon) = X(n \epsilon) + \epsilon X(n \epsilon) = X(n \epsilon) (1 + \epsilon)$

Hence:

$X(n \epsilon) = (1 + \epsilon) ^ n$

So the approximation method gives a discrete exponential growth, which converges to a continuous exponential in the limit as the mesh size goes to zero.

Note, the case we just considered has more generality than might appear at first, because (1) the ideas here are easily extended to systems of explicit first order equations, and (2) higher-order equations that are “explicit” in an extended sense – meaning that the highest-order derivative is expressed as a function of time, of the variable, and of the lower-order derivatives – can be converted into an equivalent system of explicit first-order equations.

So, is our cup half-empty or half-full? We have no toolbox of primitive formulas for building the solutions to all differential equations by finite compositions. And even for those which can be solved by formulas, there is no general method for finding the solutions. That is how the cookie crumbles. But on the positive side, there is an array of theoretical tools for analyzing and solving important classes of differential equations, and numerical methods can be applied in many cases.

The study of differential equations leads to some challenging problems, such as the Navier-Stokes equations, which describe the flow of fluids.

These are partial differential equations involving flow velocity, pressure, density and external forces (such as gravity), all of which vary over space and time. There are non-linear (multiplicative) interactions between these variables and their spatial and temporal derivatives, which leads to complexity in the solutions.

At high flow rates, this complexity can produce chaotic solutions, which involve complex behavior at a wide range of resolution scales. This is *turbulence*. Here is an insightful portrait of turbulence, by Leonardo da Vinci, whose studies in turbulence date back to the 15th Century.

Turbulence, which has been described by Richard Feynman as the most important unsolved problem of classical physics, also presents a mathematical puzzle. The general existence of solutions to the Navier-Stokes equations remains unsettled. This is one of the “millennium problems,” for which a one million dollar prize is offered: in three dimensions, given initial values for the velocity and scalar fields, does there exist a solution that is smooth and everywhere defined? There are also complications with grid-based numerical methods, which will fail to produce globally accurate results if the solutions contain details at a smaller scale than the grid mesh. So the ubiquitous phenomenon of turbulence, which is so basic to the movements of the atmosphere and the seas, remains an open case.

But fortunately we have enough traction with differential equations to proceed directly with the rate equations for Petri nets. There we will find illuminating equations, which are the subject of both major theorems and open problems. They are non-linear and intractable by formula-based methods, yet, as we will see, they are well handled by numerical methods.

category: blog