By Martin Elsman, DIKU
This application demonstrates the use of
Futhark for showing bifurcation diagrams
for a number of non-linear discrete recurrence examples that
illustrate chaotic behavior. The application builds on the Futhark
Lys Library and allows for the user
to navigate and zoom the area of interest (arrow keys, z, and
x). Currently, the application supports the following recurrence
equations, which can be altered between, dynamically, using the keys
1-6 (for some of the recurrences, an extra parameter may be
adjusted using the u and j keys):
-
Logistic map: The Logistic map takes a point x_n and computes a new point x(n+1) using the equation:
x(n+1) = r · xn · (1 - xn)
Here r is a parameter and in the setup values for r (ranging between 3.5 and 4.0) constitute values on the horizontal axis of the bifurcation diagram. The application uses the initial value x0 = 0.25 for the calculation. For different parameters r, xn will (1) converge towards a particular value, (2) result in an oscillating solution (jumping between multiple different values), or (3) result in chaotic behavior (no repeated patterns).
-
SinCos map: The SinCos map takes a point (xn,yn) and computes a new point (x(n+1),y(n+1)) using the equations:
x(n+1) = sin (xn + a · yn)
y(n+1) = cos (b · xn + yn)
Here a and b are parameters. The bifurcation diagram uses a fixed value of a = 2.82 whereas the values for b constitute values (ranging between 0 and 3) on the horizontal axis of the bifurcation diagram. The implementation uses the initial point (x0,y0) = (0.1,0.1) for the calculations. It turns out that for different parameters a and b, xn will (1) converge towards a particular value, (2) result in an oscillating solution (jumping between multiple different values), or (3) result in chaotic behavior (no repeated patterns).
-
Tent map: The Tent map takes a point xn and computes a new point x(n+1) using the equation:
x(n+1) = u · min (xn, 1-xn)
Here u is a parameter and in the setup, values for u (ranging between 1.0 and 2.0) constitute values on the horizontal axis of the bifurcation diagram. The application uses the initial value x0 = 0.1 for the calculation. For different parameters u, xn will (1) converge towards a particular value, (2) result in an oscillating solution (jumping between multiple different values), or (3) result in chaotic behavior (no repeated patterns).
-
Gaussian map: The Gaussian map takes a point xn and computes a new point x(n+1) using the equation:
x(n+1) = exp (-a · xn2) + b
Here a and b are parameters. The bifurcation diagram uses a fixed value of a = 6.2 whereas the values for b constitute values (ranging between -1 and 1) on the horizontal axis of the bifurcation diagram. The implementation uses the initial point x0 = 0.1 for the calculations. It turns out that for different parameters a and b, xn will (1) converge towards a particular value, (2) result in an oscillating solution (jumping between multiple different values), or (3) result in chaotic behavior (no repeated patterns).
-
Henon map: The Henon map takes a point (xn,yn) and computes a new point (x(n+1),y(n+1)) using the equations:
x(n+1) = 1 - a · xn2 + yn
y(n+1) = b · xn
Here a and b are parameters. The bifurcation diagram uses a fixed value of b = 0.3 whereas the values for a constitute values (ranging between 1 and 1.45) on the horizontal axis of the bifurcation diagram. The implementation uses the initial point (x0,y0) = (0.1,0.1) for the calculations. It turns out that for different parameters a and b, xn will (1) converge towards a particular value, (2) result in an oscillating solution (jumping between multiple different values), or (3) result in chaotic behavior (no repeated patterns).
-
Logistic map (interpreted): This equation is implemented using an interpreted approach where the equation is implemented using a sequence of register file instructions that are executed by a simple interpreter written in Futhark. It turns out that this interpreted approach is only a factor of two slower than the hard-coded solution that requires complete knowledge of the particular recurrence equation at compile time. The interpretation approach can be beneficial in cases where a compile-once approach is desired and where the application needs to work for different code. Following the interpretation approach, the present application can be extended to take recurrence formulas as input at runtime.
The application is quite easy to extend to cover new equations; see the source code for details.
Each supported recurrence system is defined by giving a concrete record matching the following type:
type^ sysdef 'p =
{kind: kind,
init: p, -- initial state
prj: p -> f64, -- projection of vertical value
next: f64 -> p -> p, -- parameterised recurrence
ns: (i32,i32), -- pair of warm-up iteration number
-- and hot iteration number (drawing)
p_rng: (f32,f32), -- parameter range (horizontal axis)
x_rng: (f32,f32) -- range of vertical axis
}
Many times a second, the application creates a frame for drawing. It
parallelises the work for each parameter value, each of which is
computed based on the width of the window and the range specified by
the p_rng record field. In other words, the application parallelises
the work for the columns of the window.
For each parameter value, the application first warms up the
recurrence by, iteratively (and for each parameter value in
parallel), executing the next function a number of times (given by
the first component of the ns field) starting with the value
contained in the init field. The application then applies the next
function a number of times (specified by the second component of the
ns field) and records the resulting values for drawing points in the
frame. Again, these computations are done in parallel for all columns
in the frame.
To build and run the application, do as follows:
$ futhark pkg sync
$ make
$ ./feigenbaum -i
Copyright (c) Martin Elsman, DIKU
MIT License
[1] List of Chaotic Maps. Wikipedia Article. See https://en.wikipedia.org/wiki/List_of_chaotic_maps .