Saturday, 6 June 2009

Welcome to Haskell for Maths


I have started this blog so that I can talk about my Haskell for Maths library, which is available at:

(I will probably put it on Hackage at some point, but I'm having a few problems getting the Cabal toolchain to work properly on Windows.)

Haskell for Maths is a library of Haskell code, mainly in algebra and combinatorics. (An earlier v1 of the code, accessible from that link, also contained some number theory code.)

The core building blocks of the library are the following data structures and algorithms:
  • permutations and the Schreier-Sims algorithm
  • string rewriting and the Knuth-Bendix algorithm
  • multivariate polynomials and the Buchberger algorithm for Groebner bases
  • non-commutative polynomials and Groebner-Shirshov bases

The library also contains various projects, looking at:
  • symmetries (automorphisms) of graphs and other combinatorial structures (finite geometries, designs, etc.) - in the course of which we meet a few of the sporadic finite simple groups
  • root systems and Coxeter groups
  • Chevalley groups (finite simple groups of Lie type)
  • Knot theory - calculating the Jones and HOMFLY polynomials using Temperley-Lieb and (Iwahori-)Hecke algebras
There's also further code, still in the labs, for things like:
  • Algebraic geometry, including invariant theory, Grassmannians
  • Clifford algebras
What I want to do in this blog is explain some nice maths, and how we can investigate it in Haskell.

As a taster, here's a pretty picture:

This is the Clebsch graph. It's obvious from the way it's drawn that it has a five-fold symmetry, by rotating about the centre, and several two-fold symmetries, by reflecting in various axes through the centre (eg the vertical). A graph symmetry is any way of swapping the vertices around (taking connected edges with them), that leaves the configuration as a whole looking the same. Individual vertices and edges may end up in different places, but collectively the vertices and edges are still in the same places. Anyway, it turns out that this graph has 1920 symmetries. (For example, you might be able to see that there is a symmetry that kind of interchanges the inner and the outer rings of 5 vertices, unfolding the inner star and folding the outer pentagon as it goes.)

More next time.

No comments:

Post a Comment