Sunday, March 28, 2010

Matrix and linear algebra in F#, Part II: doing linear algebra via math providers

Long story short

Suppose we are using the latest release, 1.9.9.9, which does not support linear algebra anymore in its PowerPack. But linear algebra is supported before in 1.9.7.8. Under its bin\ folder, there is a DLL named FSharp.PowerPack.Math.Providers.dll. “Math providers” means F# calls other math libraries, to be specific, an incomplete managed implementation in F#, Netlib’s Lapack+Blas and Intel MKL. The F# one is immature, while the last two are really really good! Plus Netlib’s implementation is free.

However, we cannot just use that provider dll because it has conflicts with latest PowerPack. We need to build a new one! Here are the steps:

1. Compile Netlib’s Lapack to get lapack.dll and blas.dll. Refer to this post of mine. You can also search online to download these two dlls, e.g. http://www.stanford.edu/~vkl/code/libs.html (I haven't tested this).

2. Get the source code of 1.9.7.8. Go to folder FSharp-1.9.7.8\source\fsppack\FSharp.PowerPack. Remove the old reference to FSharp.PowerPack and add two 1.9.9.9 DLLs to the reference:

FSharp.PowerPack.dll and FSharp.PowerPack.Compatibility (Because in 1.9.9.9, Compatibility module is separated out.)

Compile and you get only a few errors regarding “permutation”:

you could just define it explicitly: type permutation = int –> int

Done! Now we move on to

Use Lapack library

First make sure your project

1. references to

FSharp.PowerPack.Compatibility, FSharp.PowerPack and FSharp.PowerPack.Math.Providers.dll.

2. has lapack.dll and blas.dll in the binary output folder. E.g. Debug\ or Release\. (Technically we only need to put them under a folder .Net platform is searchable, similar to Java’s CLASSPATH.)

Finally, let’s write a simple program:

open Microsoft.FSharp.Math
let r = new System.Random()
let A = Matrix.init 4 4 (fun i j -> r.NextDouble() * 1000.0)
let Ainv = Experimental.LinearAlgebra.Inverse A
let eigen = Experimental.LinearAlgebra.EigenValues A
Although this program compiles, it gives a Not-Implemented exception on EigenValues function. (It can compute Inverse of A correctly.) This is because functions in LinearAlgebra module use managed implementation (see linear_algebra_managed.fs in lapack folder) on default. However, the managed implementation is incomplete, and not thoroughly tested.

We need to first open the lapack service:
let isSucc = Experimental.LinearAlgebra.Lapack.Start()
Put this before any computation. (Because there’s no documentation at all, I’ve read all the code in lapack folder to find this line…)

The returned bool value isSucc indicates whether the Lapack service providers successfully loads dlls for Netlib or not.

If you have Intel MKL

Put mkl_def.dll and mkl_lapack.dll under a .Net searchable folder. Notice that the wrapper is for MKL 9.1 not for 10 series.

Btw, the Lapack service provider will choose MKL if both MKL and Netlib are presented.


The Long story


.Net do have some good math libraries. They are efficient (native performance), easy to use. However, they are not free. For the free ones, there’s a Math.Net open source project, which is still under its alpha-testing phase. These open source projects seem to tend to implement all algorithms from starch in C#, rather than link to some mature ones, like Netlib’s lapack. This certainly has some advantages, like more safe code, better memory management in a .Net sense and exception handling. However, this strategy would have a long development time.

I also suspect their efficiency. I have a L-BFGS based logistic regression solver written C++, it runs 3~4 times slower if compiled into .Net using C++/CLI. Drawing a conclusion from this single case is too assertive. (I used STL and STL is slow in C++/CLI, in C++/CLI we’d better use CLI STL.) However, I still trust native libraries to perform basic linear algebra for the performance's seek.

I started to use F# from its 1.9.7.8 (The October CTP, 2009). In that release, the math provider library is already spitted out from the main PowerPack as a standalone DLL. But there’s no documentation on it, except the source code. Other math types, e.g. matrix, vector, are documented. So I didn’t know there exists such a library at first. By occasion, I found the lapack folder in the F# source. Today, I finally have some time to dig into it, get it compiled and know how to start the linear algebra service provider. Fortunately, once started, the service provider is able to automatically find the DLLs of Netlib or MKL, which is really nice.

The code is still compliable using 1.9.9.9, but I am not sure it will in the future as there are a lot of warnings mentioning deprecated language usages, e.g. use OCaml-style ‘^’to connect two strings.

As this code is under MS open source license, there would be license problems if we maintain and distribute it. So a possible solution is to rewrite the service provider and make it open source (e.g. MIT or BSD license), or, persuade MSR Cambridge or MS VS Team to continue the development.

No comments:

Post a Comment

Post a Comment