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(N²) 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 2¹²-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 (N²) 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 2¹²-point transform that took 5.8s with the naive 0(N²) 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⁻¹⁴ 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 2²⁰ - 1 length transform takes longer than the 2²⁰ length transform because algorithm resorts to three separate 2ⁿ⁺¹ 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.

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 M_ij = ±1) are also well approximated by the semi-circle law. The results of this program, illustrated in figure 12.1, demonstrate this.

The notion of the n^th-nearest neighbours Nⁿ_i of a vertex i in a graph is rigorously defined by a recurrence relation based upon the set of first nearest neighbours N¹_i ≡N_i 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 = (i_o, i _i) where i₀ ϵ Z^d and i_i ϵ II. This explicitly includes the offset i₀ of the supercell as well as the index i_i 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), i_i) and ((1,0), i_j,), 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 r_i 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 n^th -nearest neighbors that returns the singleton set for the 0^th -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 n^th-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.

Figure 12.4. The 50^th-nearest neighbour shell from a 10⁵-atom model of amorphous silicon [1] rendered using the F#for Visualization library.