F# for Scientists

Chapter 12. COMPLETE EXAMPLES

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.

FAST FOURIER TRANSFORM

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).

Discrete Fourier transform

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 ...