Sunday, March 28, 2010

Matrix and linear algebra in F#, Part I: the F# Matrix type

Every language has libraries, besides the big .Net libraries, F# has two own: the Core, which is shipped with Visual Studio 2010, and the PowerPack, which is an external library developed by MSR Cambridge and Visual Studio Team. Notice that the code quality in PowerPack is actually quite high, it is put outside the Core library because it is evolving fast. Once stable, they may be put into the Core.

Our concern is matrix and linear algebra operations. There is a matrix class in F# PowerPack. However, Microsoft didn’t officially put the documentation online. For F# 1.9.6, there is a outdated page on MSR’s website. But it doe not matter we use the old documentation, since the interface for Math haven’t change much since then.

The namespace for Math is:

Namespace Microsoft.FSharp.Math

In this namespace, we have:

1. complex numbers

2. Big rational numbers

3. vector and row-vector

4. matrix

In this post, I focus on matrix.

The real matrix:

First, Names! There is a type called matrix, which is a matrix holding double or 32-bit long float values.

There is a module called Matrix, inside which there are lots of functions to operate on an F# matrix.

There is also a function/val called matrix, which is used like a constructor to construct a new matrix from lists or arrays.

We can easily create two 3-by-3 matrices using the matrix function:

let A = matrix [ [ 1.0; 7.0; 2.0 ];
[ 1.0; 3.0; 1.0 ];
[ 2.0; 9.0; 1.0 ]; ]

let B = matrix [ [ 10.0; 70.0; 20.0 ];
[ 10.0; 30.0; 10.0 ];
[ 20.0; 90.0; 10.0 ]; ]
All the member functions and operators associated with matrix type are documented here. Here are some examples:
A+B
A-B
A*B // matrix product
A.*B // element-wise product
A * 2.0 // scalar product
2.0 * A // this is also ok
-A // negation of a matrix

let b = vector [5.;8.;9.]; // defines a vector
A*b // matrix-vector product
You can get the properties using member functions:

let dim = A.Dimensions
// val dim : int * int = (3, 3), the dimension is a tuple
let A' = A.Transpose // you can use ' in a variable name!
let nrow = A.NumRows
let ncol = A.NumCols
let Anew = A.Copy() // get a new matrix
let Aarr = A.ToArray2D() // convert to a Array2D type
let Avec = A.ToVector() // take the first column of A
let Arvec = A.ToRowVector() // take the fisrt row of A
// ToVector and ToRowVector is usually used
// when you know your matrix is actually a vector


Accessing a matrix

We can have Matlab like access to an F# matrix. One different thing is that the index starts from 0, not 1. Mathematicians like the index to start with 1, e.g. in R and Matlab. While programs like 0-based index, e.g. Numpy for Python.

// notice that the index starts at 0
A.[2,2] //The operator [,] allows access a specific
//element in the matrix, shorthand for A.Item
A.[2,2] <- 100.0 // change a value
A.[1..2,1..2] // get a sub matrix, shorthand for A.GetSlice
A.[1..2,1..2] <- matrix [[2.;3.]; [8.;9.;]] // set a sub matrix, shorthand for A.SetSlice
We also have 4 member functions: Column, Columns, Row and Rows:

A.Column 2 // Vector<float> = vector [|2.0; 1.0; 1.0|]
A.Row 2 // RowVector<float> = rowvec [|2.0; 9.0; 1.0|]
A.Columns (1,2) // starts at column 1, take 2 columns
//val it : Matrix<float> = matrix [[7.0; 2.0]
// [3.0; 1.0]
// [9.0; 1.0]]
A.Rows (1,2) // starts at row 1, take 2 columns

The Matrix module

Similar to that F# list type has a List module containing handy functions like map, fold and etc, the real matrix type matrix also has a module.

let Asum = Matrix.sum A // sum of all elements in A
let Aprod = Matrix.prod A // product of all elements in A
let C = Matrix.create 10 10 1.0 // create a matrix with 1s
let table = Matrix.init 9 9 (fun i j -> (float i + 1.) * (float j + 1.))
// create a matrix with a function
let I10 = Matrix.identity 10 // 10 1s one diagnal
let Atrace = Matrix.trace A // trace sum
let Asqr = Matrix.map (fun x -> x*x) A // A^2
And there are some repetitions on the member function/operators of matrix type. E.g. Matrix.add, Matrix.set, Matrix.get, Matrix.toVector, Matrix.toRowVector, Matrix.transpose, etc.

Sparse matrix

let D = Matrix.initSparse 3 3 [ (0,0,1.0); (1,1,2.0); (2,2,3.0); ]
// init a sparse 3-by-3 matrix
//val it : matrix = matrix [[1.0; 0.0; 0.0]
// [0.0; 2.0; 0.0]
// [0.0; 0.0; 3.0]]
D.IsSparse // sparse test
let E = Matrix.initSparse 100000 100000 [ (0,0,1.0); (1,1,2.0); (2,2,3.0); ]
let Esum = Matrix.sum E

However, map, fold, exists, .. are not supported on sparse matrix.

Int Matrix, BigNum Matrix, and others

To know about Generic matrix, you may want to read another post of mine:

http://fdatamining.blogspot.com/2010/03/f-inumerics-interface-and-matrix-class.html

which also discusses some implementation details of the Matrix class, and how to define your own matrix, e.g. a Pixel matrix.

4 comments: