This chapter details several complete programs that demonstrate some of the most importants forms of scientific computing whilst also leveraging the elegance of the F# language and the power of the .NET platform.
The program developed in this section combines a core concept in scientific comput-ing with a core concept in computer science:
Spectral analysis: computing the Fourier transform.
Divide and conquer algorithms.
The Fourier transform is one of the most essential tools in scientific computing, with applications in all major branches of science and engineering as well as computer science and even mathematics. This section describes the development of an efficient implementation of the Fourier transform known as the Fast Fourier Transform (FFT).
In its simplest form, the Fourier transform
This direct summation algorithm is referred to as the Discrete Fourier Transform (DFT) and is composed of 0(N2) operations, i.e. this algorithm has quadratic asymptotic time complexity.
This naive algorithm may be implemented as a simple F# function:
> #light;; > open System;; > open Math;; > let dft ts = let N = Array.length ts [|for k in 0 .. Array.length ts - 1 -> let mutable z = Complex.zero for n=0 to N-l do let w = 2.0 * Math.PI / float N * float n * float k z <- z + ts.[n] * complex (cos w) (sin w) z|];; val dft : Complex array -> complex array
For example, the dft
function correctly computes the Fourier series of a sine wave:
> [| for i in 0 .. 15 -> complex (float i / 8.0 * Math.PI |> sin) 0.0|] |> dft;; val it : complex array = [|0; 8i; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; −8i|]
This output assumes the use of the pretty printer for complex numbers given in section 9.11.3.
However, this implementation is very slow, taking 5.8s to compute a simple 212-point DFT:
> [| for n in 1 .. 4096 -> complex (float n) 0.0 |] |> time (ignore << dft);; Took 5 792ms
As we shall see, the performance of this implementation can be greatly improved upon.
As always, algorithmic optimizations are the best place to search for performance improvements. In this case, the naive 0 (N2) algorithm may be replaced by an 0(N log N) divide-and-conquer algorithm when N is an integral power of two. This algorithm, often referred to as the radix-2 Fast Fourier Transform (FFT) has been the foundation of numerical Fourier transforms for at least 200 years. The FFT algorithm splits an n -point FFT into two
The prefactors
Using conventional rearrangements, this algorithm may be decomposed into an initial shuffle of the input followed by a sequence of traversals over the input data.
The sort and subsequent rewrites of the array are most easily written in terms of swaps and in-place rewrites, both of which may be elegantly added to the built-in Array
module:
> module Array = let swap (a : 'a array) i j = let t = a. [i] a. [i] <- a. [j] a. [j] <- t let apply f a = for i=0 to Array.length a-1 do a. [i] <- f a. [i];; module Array : begin val swap : 'a array -> int -> int -> unit val apply : ('a -> 'a) -> 'a array -> unit end
An initial sort can reorder the elements of the input array in lexicographic order by the bits of their indices. This may be implemented as a simple F# function that uses bit-wise integer operations:
> let bitrev a = let n = Array.length a let mutable j = 0 for i=0 to n-2 do if i<j then Array.swap a i j let rec aux m j =
let m = m/2 let j = j ^^^ m if j &&& m = 0 then aux m j else j j <- aux n j;; val bitrev : 'a array -> unit
The inner loop of the algorithm operates on a Complex array
and is easily written in F# using its overloaded operators to handle complex arithmetic:
> let fft_aux (a : Complex array) n j sign m = let w = let t = Math.PI * float (sign * m) / float j complex (cos t) (sin t) let mutable i = m while i < n do let ai = a. [i] let t=w*a.[i+j] a. [i] <- ai + t a. [i + j] <- ai - t i <- i + 2*j;; val fft_aux : Complex array -> int -> int -> int -> int -> unit
The following fft_pow2
function uses the bitrev
and loop
functions to compute the FFT of vectors with lengths that are integral powers of two:
> let fft_pow2 sign a = let n = Array.length a bitrev a let mutable j = 1 while j < n do for m = 0 to j - 1 do fft_aux a n j sign m j <- 2 * j;; val fft_pow2 : int -> Complex array -> unit
The previous example of a 212-point transform that took 5.8s with the naive 0(N2) algorithm now only takes 0.009s:
> [| for n in 1 . . 4096 -> complex (float n) 0.0 |] |> time (ignore << fft_pow2 1);; Took 9ms
In fact, this divide-and-conquer algorithm is so much faster that it can solve problems that were completely infeasible with the previous implementation:
> [| for n in 1 .. 1048576 -> complex (float n) 0.0 |]
|> time (ignore << fft_pow2 1);; Took 4 781ms
However, this implementation can only be applied when N is an integral power of two.
The Fourier transform of an arbitrary-length signal may be computed by rephrasing the transform as a convolution and zero padding the convolution up to an integral power of two length. Note that zero padding a convolution is exact. The DFT may be expressed as a convolution:
where:
The factors
> let bluestein_sequence n = let s = Math.PI / float n [|for k in 0 .. n-1 -> let t = s * float(k * k) complex (cos t) (sin t)|];; val bluestein_sequence : int -> complex array
The following function gives the next power of two above the given number:
> let rec next_pow2 = function | 0 -> 1 | n -> 2 * next_pow2(n / 2);; val next_pow2 : int -> int
Padding is accomplished using the following function:
> let pad n nb (w : complex array) = function | i when i < n -> w. [i] | i when i >nb - n ->w.[nb-i]
| _ -> Complex.zero val pad : int -> int -> complex array -> int -> complex
These can be combined to compute the Fourier transform of an arbitrary length signal in-place by zero padding its convolution up to an integral power of two and using the fft_pow2
function:
> let bluestein a = let n = Array.length a let nb = pow2_atleast(2*n - 1) let w = bluestein_sequence n let y = pad n nb w |> Array.init nb fft_pow2 (-1) y let b = Array.create nb Complex.zero for i=0 to n-1 do b.[i] <- Complex.conjugate w.[i] * a.[i] fft_pow2 (-1) b let b = Array.map2 (*) b y fft_pow2 1 b let nbinv = complex (1.0 / float nb) 0.0 for i=0 to n-1 do a.[i] <- nbinv * Complex.conjugate w.[i] * b.[i];; val bluestein : Complex array -> unit
For the forward transform, the real and imaginary parts are exchanged using the following swapri
function:
> let swapri a = Array.apply (fun z -> complex z.i z.r) a;; val swapri : complex array -> unit
The following is_pow2
function tests if a number is an integral power of two using the fact that only such numbers share no bits with their predecessor:
> let is_pow2 n = n &&& n-1 = 0;; val is_pow2 : int -> bool
For example, filtering out the powers of two from a sequence of consecutive integers using the is_pow2
function:
> List.filter is_pow2 [1 .. 1000];; val it : int list = [1; 2; 4; 8; 16; 32; 64; 128; 256; 512]
These routines may be combined to compute an arbitrary FFT:
> let fft sign a = let n = Array.length a if is_pow2 n then fft_pow2 sign a else
if sign=l then swapri a bluestein a if signal then swapri a;; val fft : int -> Complex array -> unit
This fft
function may be applied to arbitrary-length complex arrays to compute the Fourier transform in O(N log N) time using the given sign to determine the direction of the transform. Consequently, it is productive to wrap this function in fourier
and if ourier
functions that compute forward and reverse transforms using the appropriate signs:
> let fourier a = fft 1 a; a;; val fourier : Complex array -> Complex array > let ifourier a = fft (-1) a; a;; val ifourier : Complex array -> Complex array
Note that these functions return the input array because this is often useful and not because they are out-of-place transforms.
The new fourier
function is most easily tested by comparing its input with that of the dft
function on random input:
> let rand = new System.Random();; val rand : System.Random > let a = [|for i in 0 . . 14 -> complex (rand.NextDouble()) (rand.NextDouble 0) |];; val a : Complex array > fourier (Array.copy a) |> Seq.map2 (-) (dft (Array.copy a)) |> Seq.map Complex.magnitude;; |> Seq.fold max 0.0;; val it : complex = 1.754046975e-14
The maximum numerical error of 1.75 × 10−14 introduced by the more efficient fourier
function is clearly very small.
This implementation remains very fast:
> [|for n in 1 .. 4096 ->
complex (float n) 0.0|] |> time (ignore << fourier);; Took 9ms > [|for n in 1 . . 1048576 -> complex (float n) 0.0|] |> time (ignore << fourier);; Took 4 781ms > [|for n in 1 .. 1048575 -> complex (float n) 0.0|] |> time (ignore << fourier);; Took 30227ms
Despite having a smaller number of elements, the 220 - 1 length transform takes longer than the 220 length transform because algorithm resorts to three separate 2n+1 length transforms instead.
As we have seen, the FFT is an excellent algorithm to introduce many of the most important concepts covered in the earlier chapters of this book. In particular, algorithmic optimization is a source of enormous performance improvements in this case.
The program developed in this section combines two related subjects that are both core concepts in scientific computing:
Linear algebra: eigenvalues.
Random matrix theory.
The importance of linear algebra is widely known. Many naturally occurring phenomena can be modelled in terms of vectors and matrices. Most notable, perhaps, is the representation of quantum-mechanical operators as matrices, the eigenvalues of which are well known to have special importance [10]. Solving matrix problems can require various different forms of matrix manipulation, particularly forms of factorization. For example, one prevelant task is the computation of eigenvalues that we examine here. The eigenvalues of a Hamiltonian quantify the energy levels of the physical system.
Random matrix theory is a fascinating branch of mathematics dedicated to studying the properties of matrices with elements drawn from known probability distributions. Predictions about eigenvalue correlations and distributions are of great practical importance and random matrix theory has been responsible for several laws that turned out to be far more widely applicable than expected [2, 19].
In this section, we present an F# program that generates random matrices and uses a library to compute their eigenvalues before compiling the eigenvalue distribution and visualizing the results in Excel.
As discussed in chapter 9, the defacto-standard library for linear algebra on the .NET platform is the Extreme Optimization library from Numeric Edge. Consequently, we shall use this library to handle the generated matrix and compute its eigenvalues. Before using the Extreme Optimization library, the DLL must be loaded:
> #light;; > #I @"C:Program FilesExtreme Optimization Numerical Libraries for .NETin";; > #r "Extreme.Numerics.dll";;
Routines for handling symmetric matrices and computing their eigenvalues are in the following namespace:
> open Extreme.Mathematics.LinearAlgebra;;
The following eigenvalues
function computes the eigenvalues of a symmetric n × n matrix with elements taken randomly from the set {-1,1}:
> let eigenvalues n = let m = new SymmetricMatrix(n) let rand = new System.Random() for i=0 to n-1 do for j=i to n-1 do m.Item(i, j) <- float(2*rand.Next(2) - 1) m.GetEigenvalues ();; val eigenvalue : int -> GeneralVector
The Item
property for the SymmetricMatrix
class is overloaded and F# is unable to resolve the overload so the a.[i]
< - x syntax cannot be used. This problem is circumvented by calling a. Itern (i)
<- x directly.
The eigenvalue solver in this library is so fast that a relatively large matrix can be used:
> let eigs = eigenvalues 1024;; val eigs : Complex.ComplexGeneralVector
The following get
function can be used to fetch an element from a map using the default value 0
for unspecified elements:
> let get (m : Map<'a, int>) i = try m. [i] with | Not_found -> 0;; val get : Map<'a,int> -> 'a -> int
This simple and asymptotically efficient implementation of a sparse container (e.g. a vector in this case) is adequate here because the collation of results is not performance critical. However, high-performance programs requiring faster sparse vector and matrix routines would benefit significantly from using an implementation such as that provided by the Extreme Optimization library.
The following inc
function increments an element in a sparse map:
> let inc m i = Map.add i (1 + get m i) m;; val inc : Map<'a,int> -> 'a -> Map<'a,int>
The following function accumulates the distribution of elements in a vector:
> let density_of (seq : GeneralVector) = let aux m x = x + 0.5 |> floor |> inc m Seq.fold aux Map.empty seq |> Map.to_array;; val density_of : GeneralVector -> (float * int) array
The distribution of the eigenvalues eigs
of the matrix is then given by:
> let density = density_of eigs;; val density : (float * int) array
The results are most easily visualized by injecting them directly into a running Excel spreadsheet.
The simplest way to visualize the results generated by this program is using Excel. Fortunately, the Excel automation facilities provided by .NET make it very easy to inject results from an F# program directly into the cells of an Excel spreadsheet, as described in chapter 11.
The appropriate assembly must be loaded:
> #r "Excel.dll";;
The relevant functions are in the following namespaces:
> open Excel;; > open System.Reflection;;
Injecting results into a spreadsheet requires an application class, workbook and worksheet:
> let app = new ApplicationClass(Visible = true);; val app : ApplicationClass
A new workbook may be created with:
> let workbook = app.Workbooks.Add(XlWBATemplate.xlWBATWorksheet);;
val workbook : Workbook
The first worksheet in the spreadsheet is given by:
> let worksheet = (workbook.Worksheets.[box 1] :?> _Worksheet);; val worksheet : _Worksheet
The following function allows a cell in the spreadsheet to be set:
> let set i j v = worksheet.Cells.Item(j, i) <- box v;; val set : 'a -> 'b -> 'c -> unit
The following line iterates over the density of eigenvalues, filling in the spreadsheet cells with the value and density of eigenvalues:
> density |> Seq.iteri (fun j (a, b) -> set 1 (j+1) a set 2 (j+1) b);;
Excel can then be used to analyze and visualize the data.
A famous result of random matrix theory is the semi-circle law of eigenvalue densities for random n × n matrices from the Gaussian Orthogonal Ensemble (GOE):
Although the derivation of the semi-circle law only applies to GOE matrices, the distributions of the eigenvalues found by this program (for Mij = ±1) are also well approximated by the semi-circle law. The results of this program, illustrated in figure 12.1, demonstrate this.
The program developed in this section combines four important algorithmic concepts that are commonly encountered in scientific computing:
Set-theoretic operations: union, intersection and difference.
Graph-theoretic operations: nth-nearest neighbours.
Implicit data structures: finite data represent an infinite graph.
Dynamic programming: a form of divide and conquer that handles overlapping subproblems.
High-performance real-time interactive visualization that runs concurrently with the main computation.
The graph-theoretic problem of finding the nth-nearest neighbours allows useful topological information to be gathered from many forms of data produced by other scientific computations. For example, in the case of simulated atomic structures, where topological information can aid the interpretation of experimental results when trying to understand molecular structure. Such topological information can also be used indirectly, in the computation of interesting properties such as the decomposition of correlation functions over neighbour shells [5], and shortest-path ring statistics [7].
We shall describe our unconventional formulation of the problem of computing the nth-nearest neighbours of atoms in an atomic structure simulated under periodic boundary conditions before describing a program for solving this problem and presenting demonstrative results.
The notion of the nth-nearest neighbours Nni of a vertex i in a graph is rigorously defined by a recurrence relation based upon the set of first nearest neighbours N1i ≡Ni of any atom i:
Figure 12.2. Conventionally, atoms are referenced only by their index i ϵ I={l...N } within the supercell. Consequently, atoms i,j ϵ I at opposite ends of the supercell are considered to be bonded.
As a recurrence relation, this computational task naturally lends itself to recursion. As this recurrence relation only makes use of the set-theoretic operations union and difference, the F# data structure manipulated by the recursive function is most naturally a set (described in section 3.4).
In order to develop a useful scientific program, we shall use an infinite graph to represent the topology of a d -dimensional crystal, i.e. a periodic tiling. Computer simulations of non-crystalline materials are typically formulated as a crystal with the largest possible unit cell, known as the supercell. Conventional approaches to the analysis of these structures reference atoms by their index i ϵ I ={1... N} within the origin supercell. Edges in the graph representing bonded pairs of atoms in different cells are then handled by treating displacements modulo the supercell (illustrated in figure 12.2). However, this conventional approach is well-known to be flawed when applied to insufficiently large supercells [7, 8], requiring erroneous results to be identified and weeded out manually.
Instead, we shall choose to reference atoms by an index i = (io, i i) where i0 ϵ Zd and ii ϵ II. This explicitly includes the offset i0 of the supercell as well as the index ii within the supercell (illustrated in figure 12.3). Neighbouring vertices in the graph representing the topology are defined not only by the index of the neighbouring vertex but also by the supercell containing this neighbour (assuming the origin vertex to be in the origin supercell at { 0}d).
Figure 12.3. We use an unconventional representation that allows all atoms to be indexed by the supercell they are in as well as their index within the supercell. In this case, the pair of bonded atoms are referenced as (0, 0), ii) and ((1,0), ij,), i.e. with i in the origin supercell (0,0) and j in the supercell with offset (1,0).
We shall now develop a complete program for computing the n th-nearest neighbours of a given vertex with index i from a list of lists ri of the indices of the neighbours of each vertex.
A common design pattern in programs that include lexers and parsers involves the parser and main program depending upon the definition of a core data structure. This pattern is most elegantly implemented by placing the definition of the data structure in a separate compilation unit that both the parser and the main program depend upon.
In this case, the data structure used to represent an atomic configuration must be shared between the parser and main program. Consequently, this data structure is defined in a separate compilation unit called "model.fs":
module Model type coord = { index: int; offset: vector } type vertex = { position: vector; neighbors: Set<coord> } type t = { supercell: vector; vertices: vertex array }
The coord
type represents a vertex in the infinite graph with the given integer index into the vertex array and the given supercell offset vector. The elements of the offset vector are integers but are stored as floating point numbers in this case simply because subsequent computations are made easier by the use of the uniform, built-in vector
type.
The vertex
type represents a vertex in the origin supercell of the graph and is quantified by the vector coordinate of the vertex and its set of neighbors.
The type t represents a complete model structure with the given supercell dimensions and array of vertices in the origin tile.
The format read by this program is in Mathematica syntax. Although the lexer and parser could handle their input in a generic way, performance can be significantly improved by specializing them to the particular structure of expression used to represent a model in order to avoid creating a large intermediate data structure, i.e. this is a deforesting optimization.
The parser begins by opening the Model
module to simplify the use of its data structures:
%{ open Model %}
The types and values of tokens are then defined:
%token <float> REAL
%token COMMA OPEN CLOSE
The start point of the grammar and the type returned by its action are defined before the grammar itself is described:
%start system %type <t> system %%
In this case, the grammar is most easily broken down into vectors, neighbors, vertices and a whole system. A vector is taken to be a 3D vector written in Mathematica's List
syntax:
vec3 : | OPEN REAL COMMA REAL COMMA REAL CLOSE { vector [$2; $4; $6] } ;
A neighbor is composed of its position and index, again represented by nested Mathematica lists:
neighbor: | OPEN vec3 COMMA REAL CLOSE { { offset = $2; index = int $4 - 1 } } ;
Note the use of the overloaded int
function to convert a value of any suitable type into an int
.
The neighbors of a vertex are simply a list of comma separated values:
neighbors: { [] } | neighbor { [$1] } | neighbor COMMA neighbors { $1 :: $3 } ;
Similarly, a vertex and list of vertices are a vector position and sequence of neighbors and a comma-separated list, respectively:
vertex: | OPEN vec3 COMMA OPEN neighbors CLOSE CLOSE { { position = $2; neighbors = set $5 } } ; vertices: | vertex { [$1] } j vertex COMMA vertices { $1 :: $3 } ;
Note the use of the set
function to convert any sequence into a Set
.
Finally, a whole system is composed of the supercell dimensions (as a vector) and a list of vertices:
system: | OPEN vec3 COMMA OPEN vertices CLOSE CLOSE { { supercell = $2; vertices = Array.of_list $5 } } ;
The grammatical structure of the format could have been parsed generically into a more general purpose data structure and then dissected by F# functions in the main program but this task is better suited to the optimizing compilation of grammars by a parser generator such as fsyacc
.
The lexer is very simple, handling only numbers, commas and braces. The lexer uses the definitions of tokens from the parser:
{ open Parser }
A regular expression real
handles both integers (sequences of digits) and fractional numbers (with a decimal point) and also permits a preceding minus sign for negative numbers:
let space = [' ' ' ' ' ' ' '] let digit = ['0'-'9'] let real = '-'? (digit+ | digit+ '.' digit*)
More sophisticated regular expressions could be used but these suffice for this particular example.
The lexer itself simply reduces a character stream to lexical tokens in the simplest possible way:
rule token = parse | space { token lexbuf } | real { REAL(Lexing.lexeme lexbuf |> float) } | ',' { COMMA } | '{' { OPEN } | '}' { CLOSE }
The first case in this lexer matches whitespace using the space
regular expression and calls the token
rule of the lexer recursively in order to ignore the whitespace and return the next valid token. The second case matches the real
regular expression and converts the matched string into a float
and stores it in a Real
token. The three final cases convert characters into tokens.
The main program in "nth.fs" provides an Nth
module that parses an input file and computes the neighbors of a vertex:
#light
The following file is used for input:
let filename = __SOURCE_DIRECTORY__ + @"cfg-100k-aSi.txt"
The parser is used to convert the input file into the definition of a model structure:
let system = use stream = System.IO.File.OpenRead filename use reader = new System.IO.BinaryReader(stream) let lexbuf = Lexing.from_binary_reader reader try Mmaparse.system Mmalex.token lexbuf with | Parsing.Parse_error -> let p = Lexing.lexeme_end_p lexbuf eprintf "Error at line %d " p.Line exit 1
In the event of a grammatical error in the input file, the Parse_error
exception is raised by the parser. Handling this exception and printing out a descriptive error message makes this program more user friendly.
The core of the program is the function that computes the n th -nearest neighbours. This functionality relies upon the definition of the model type from the Model
module:
open model
The core of the program is simplified by some simple auxiliary functions. The first such function displaces a vertex from the origin supercell into a different supercell:
let displace i j = { j with offset = i.offset + j.offset }
This displace
function is used when looking up the neighbor j
of a given vertex i
in any supercell via the neighbors of its mirror image in the origin supercell, in order to displace it to the appropriate supercell.
Next, a unions
function that computes the n-ary union of a sequence of sets:
let unions : (seq<Set<coord>> -> Set<coord Seq.fold Set.union Set.empty
As this is a form of dynamic programming, the nth
function is ideally suited to memoization:
let memoize f = let m = Hashtbl.create 1 fun k -> match Hashtbl.tryfind m k with
| Some f_k -> f_k | None -> let f_k = f k m.[k] <- f_k f_k
Finally, the nth
function itself is almost a direct implementation of the mathematical definition of nth -nearest neighbors that returns the singleton set for the 0th -nearest neighbor of any vertex, looks up the nearest neighbours for n = 1 and breaks the general problem into smaller but overlapping subproblems for n > 1:
let rec nth = memoize (fun n -> memoize (fun i -> match n with | 0 -> Set.singleton i | 1 -> system.vertices.[i.index].neighbors |> Set.map (displace i) | n -> let s1, s2 = nth (n-1) i, nth (n-2) i unions (Seq.map (nth 1) s1) - s2 - s1))
This example clearly demonstrates the brevity of the F# programming language, with a complete lexer, parser and computational algorithm fitting in such a tiny amount of code. However, the F# programming language is unique in combining this brevity with incredible expressiveness and performance. This is most easily demonstrated by including a real-time interactive visualization of the results that is updated as they are computed.
The simplest way to handle this and many other forms of vizualization is using the F# for Visualization library from Flying Frog Consultancy.
The following preamble is required to reference libraries and open relevant names-paces:
#I "C:ProgramFilesReference AssembliesMicrosoft Frameworkv3.0" #R "C:Program FilesFlyingFrogFlyingFrog.Graphics.dll" open System.Windows.Media open System.Windows.Media.Media3D open FlyingFrog.Graphics3D
The following line of code spawns a concurrent visualization that may be transparently updated, with all thread-related issues handled automatically by the F# for Visualization library:
let viz = Show(Group [])
This visualization will represent each of the nth-nearest neighbors as a tiny sphere:
let sphere = Shape(Sphere.make 0, Brushes.White)
The argument to the Sphere.make
function dictates the level of tesselation (as described in chapter 7) and, in this case, a coarse tesselation is used as this is satisfactory for displaying large numbers of small spheres.
Any vertex may be chosen as the origin and, in this case, the vertex with zero index in the origin supercell is used:
let i = {offset=vector [0.0; 0.0; 0.0]; index=0}
The following position
function computes the actual 3D coordinates of a vertex from its index and supercell offset:
let position c = system.vertices. [c.index] .position + system.supercell .* c.offset
Note the use of the . * operator for element-wise multiplicatio of a pair of vectors.
The following plot
function computes the n th-nearest neighbours of the vertex i, builds a scene graph with a sphere at the position of each vertex and sets the scene graph as the current scene for the visualization that was spawned using the Scene
property of the viz object:
let plot n = let ns = nth n i let at c = let r = position c - position i let r = 0.02 * r let move = TranslateTransform3D(r. [0] , r. [1] , r. [2]) let scale = ScaleTransform3D(0.05, 0.05, 0.05) Transform(scale.Value * move.Value, sphere) viz.Scene <- Group(Seq.map at ns)
An animation of the n th-nearest neighbors up to n = 40 may then be visualized using:
for n in 0 .. 4 0 do plot n
Finally, the following function is used to join the GUI thread with the main thread to keep the whole application alive until the visualization is closed:
FlyingFrog.Graphics.Run()
This is all of the code required to produce a high-performance real-time interactive 3D visualization of the results, illustrated in figure 12.4.
The program developed in this section combines two useful concepts found in scientific computing:
Chaotic behaviour from a simple system.
Simple visualization.
The logistic map is a polynomial mapping that illustrates how chaotic behaviour can arise from very simple dynamics. The logistic map is described by a single mathematical definition:
where xn is the population at time n, r is a positive constant.
This simple relationship captures two effects from population biology:
reproduction where the population will increase at a rate proportional to the current population when the population size is small.
starvation (density-dependent mortality) where the growth rate will decrease at a rate proportional to the value obtained by taking the theoretical "carrying capacity" of the environment less the current population.
The following program simulates the logistic map and visualizes the results as simply as possible, using only Windows Forms. Although it is a complete Windows Forms application, this program can be run directly from an F# interactive session without any batch compilation.
The program is written in the #light syntax and opens two namespaces to simplify the subsequent code:
> #light;; >_open_System.Drawing;; >_open_System.Windows.Forms;;
A generic pixel format is used for the form even though the output of this program is monochrome:
> let format = Imaging.PixelFormat.Format24bppRgb;; val format : Imaging.PixelFormat
The bitmap_of
function creates a new bitmap with the dimensions of the given rectangle r
and applies the given function f
to fill the bitmap:
> let bitmap_of draw (r : Rectangle) = let bitmap = new Bitmap(r.Width, r.Height, format) draw bitmap bitmap;; val bitmap_of : (Bitmap -> unit) -> Rectangle -> Bitmap
The resize
function is an event-driven callback that replaces the given bitmap reference b, filling it in using the higher-order bitmap_of
function and redraws the given form w:
> let resize f (b : Bitmap ref) (w : #Form) _ = b := bitmap_of f w.ClientRectangle w.Invalidate();; val resize : (Bitmap -> unit) -> Bitmap ref -> #Form -> 'b -> unit
The paint
function is an event-driven callback that draws the bitmap b
onto a
form using its event argument e
:
> let paint (b : Bitmap ref) (v : #Form) (e : PaintEventArgs) = let r = e.ClipRectangle e.Graphics.Drawlmage(!b, r, r, GraphicsUnit.Pixel);; val paint : Bitmap ref -> #Form -> PaintEventArgs -> unit
The make_raster
function creates a form and a bitmap and registers the resize, paint and key down callbacks:
> let make_raster title f = let form = new Form(Text=title, Visible=true) let bitmap = ref (bitmap_of f form.ClientRectangle)
form.Resize.Add(resize f bitmap form) form.Paint.Add(paint bitmap form) form.KeyDown.Add(fun e -> if e.KeyCode = Keys.Escape then form.Close()) form;; val make_raster : string -> (Bitmap -> unit) -> Form
The function that determines the evolution of a population from one time step to the next may be written:
> let f r x = r * x * (1.0 - x);; val f : float -> float -> float
The draw
function is responsible for filling in the pixels of the bitmap and will be invoked when it is passed as the argument to the bitmap_of
function:
> let draw (bitmap : Bitmap) = let w, h = bitmap.Width, bitmap.Height for j=0 to h-1 do for i=0 to w-1 do bitmap.SetPixel(i, j, Color.White) for i=0 to w-1 do let r = 2.4 + float i / float w * 1.6 for j=0 to h-1 do let y = (float j + 0.5) / float h let y = nest 1000 (f r) y let j = int_of_float ((1.0 - y) * float h) bitmap.SetPixel(i, j, Color.Black);; val draw : Bitmap -> unit
This draw
function uses the nest
combinator from section 6.1.1. Finally, a Windows form visualizing the logistic map may be created using the make_raster
function:
> let form = make_raster "Logistic map" draw;; val form : Form
The result is illustrated in figure 12.5.
The functions that make up this program could have been simplified slightly by defining the draw
function first and calling it explicitly from the functions relating to the paint callback. However, this would prevent reuse of the code. Specifically, parameterizing the bitmap_of
function used to fill the bitmap over the draw
function that does the filling allows different draw
functions to be used.
The program developed in this section combines two useful concepts found in scientific computing:
Simulation of particle dynamics.
High-performance real-time interactive visualization that runs concurrently with the main computation.
The following program simulates dynamics of a system of non-interacting particles and visualizes the results interactively and in real time using the F# for Visualization library. Although this is a complete GUI application, this program can be run directly from an F# interactive session without any batch compilation.
The program begins by referencing the F# for Visualization library:
#light #I "C:Program FilesReference AssembliesMicrosoft Frameworkv3.0" #I @"C:Program FilesFlyingFrog" #R @"FlyingFrog.Graphics.dll"
The following namespaces are opened in order to simplify the subsequent code:
open System.Windows.Media open System.Windows.Media.Media3D open FlyingFrog.Graphics3D
The particles will bounce around on a 3D surface quantified by the following function:
let f x z = let r = 5.0 * sqrt(x*x + z*z)
let sinc = function | 0.0 -> 1.0 | x -> sin x / x sinc r + 0.01 * sin x + 3e-3*r*r - 1.12
The position and velocity of each particle are encapsulated in the following record type
:
type particle = { p: Vector3D; v: Vector3D }
All of the particles have the same radius:
let size = 0.015
The following function creates a new randomly-placed particle:
let rand = new System.Random() let spawn _ = let f() = rand.NextDouble() * 0.02 - 0.01 { p = Vector3D(f() , 3.0, f ()); v = Vector3D(0.0, 0.0, 0.0) }
The current state of the particle system is represented by an array:
let state = Array.init 100 spawn
Gravity is quantified by the following vector:
let gravity = Vector3D(0.0, −1.0, 0.0)
Air resistance is quantified by the following number:
let air_loss = 0.9
Energy lost by collision with the floor is quantified by the following number:
let bounce_loss = 0.99
When the dynamics of a particle are integrated over a time span that includes a collision, the simulation will be subdivided down to time spans below the following value:
let max_dt = le-3
The following numbers are the minimum velocity and minimum height, below which particles will be respawned to keep the simulation interesting:
let min_v2, min_h = le-3, le-3
The following function integrates the equations of motion for a single particle a for a time step of length dt
, including acceleration due to gravity and damping of the velocity:
let rec update dt ({p=P; v=v} as a) = let p = p + dt *v+ 0.5 * dt*dt * gravity
let v = air_loss ** dt * (v + dt * gravity)
Note how the record fields p and v are extracted in a pattern match along with the record a itself using a named subpattern (see section 1.4.2.2).
The height of particle above the floor at the x, z coordinate of the particle is used to test for impact:
let height = p.Y - f p.X p.Z - size if v.LengthSquared < min_v2 && height < min_h then spawn() else if height >= 0.0 then { p = p; v = v } else if dt > max_dt then let f = update (dt / 2.0) f(f a) else let n = surface_normal f (p.X, p.Z) let d = Media3D.Vector3D.DotProduct(n, v) if d > 0.0 then {p=p; v=v} else { p = p; v = bounce_loss * (v - 2.0 * d * n) }
In particular, if the time interval dt spanning a collision is greater than max_dt
then the time interval is recursively bisected. This is a seemingly-trivial addition that is very easily implemented in F#. However, this part of the algorithm is of critical importance. The time integrator is exact to within numerical error for quadratic behaviour and very accurate for the slightly-damped ballistic behaviour of a flying particle but wildly inaccurate for collisions, when the velocity of the particle is instantaneously replaced at some interim moment in time. By recursively bisecting time intervals that span collisions, the collision is limited to a single short time interval where the error in time integration is much smaller. Real scientific simulations of particle systems often use similar tricks to greatly improve the accuracy of the simulation with minimal adverse effect on performance [8].
The F# for Visualization library is specifically designed to handle real-time simulations and, consequently includes an accurate timer. This timer is represented by a curriedfunction delta_timer
. Applying the first argument () todelta_timer
returns a function that gives the time since it was last invoked. Consequently, this delta_timer
function can be used to create many independent timers. In this case, we need only one:
let dt = FlyingFrog.Timer.delta_timer()
The following function calculates a transformation matrix that will be used to scale a scene graph representing a unit sphere to the size of a particle and then translate it to the particle's position in 3D space:
let particle p = ScaleTransform3D(size, size, size).Value * TranslateTransform3D(p.p).Value
The Show3D
constructor from the F# for Visualization library spawns a visualization that runs concurrently with the current thread. In this case, the scene is initially empty:
let g = Show(Group [])
The following scene graph is a smooth icosahedron that will be used to visualize each particle in the simulation:
let sphere = let color = System.Windows.Media.Brushes.White Shape(Sphere.make 0, color)
The following scene graph is a tesselation of a relevant part of the floor that will be used in the visualization:
let floor = let s = −3.0, 3.0 let color = System.Windows.Media.Brushes.Red Shape(plot3d 128 f s s, color)
The following function simulates the particle dynamics by looping indefinitely and repeatedly replacing the scene graph that is being rendered by the concurrent visualization:
let simulate () = while true do System.Threading.Thread.Sleep(30) let particles = [|for p in state -> Transform(particle p, sphere)|] g.Scene <- Group[Group particles; floor] let dt = dt() for i=0 to state.Length-1 do state, [i] <- update dt state, [i]
The simulation is run in a new background thread:
let simulator = let thread = new System.Threading.Thread(simulate) thread.IsBackground <- true thread.Start ()
As the simulation thread is a background thread and the visualization thread is (by default) a foreground thread, the program will run until the visualization is closed by the user, at which point the foreground visualization thread will die and the background simulation thread will be terminated.
Finally, the following function is used to join the GUI thread with the main thread to keep the whole application alive until the visualization is closed:
FlyingFrog.Graphics.Run()
Figure 12.6. Real-time interactive simulation and visualization of non-interacting particles bouncing on a 3D surface.
The result is illustrated in figure 12.6.