Google Summer of Code 2014 – FLINT
This year I am applying to take part in Google Summer of Code (GSoC) over the summer, working as part of the FLINT project. FLINT is a C library which contains highly optimised implementations of algorithms to perform number theoretic tasks. For example, FLINT was used a used as part of a project to compute the first one trillion congruent numbers (assuming BSD). One of main techniques used to compute these congruent numbers was by looking at the coefficients of the Fourier expansion of an associated modular form (a function from the upper half plane to the complex numbers satisfying some nice conditions). Now one of the interesting things about modular forms that make them easier to work with is the fact that they form a finite dimensional vector space over the complex numbers. The project I’m hoping to is actually related to this in a slightly tangential way. One way to find a nice basis for the space of -expansions of modular forms uses the concept of the saturation of a module in an essential way, this in turn can be computed using by finding the Hermite normal form of a matrix. The Hermite normal form of a matrix is the unique matrix obtained from it by unimodular (row/column) operations satisfying some conditions on its entries. So by computing Hermite normal forms quickly we can find bases for spaces of -expansions more easily but there are also a whole raft of other applications within algebraic number theory, cryptography and yet more areas. The project I am hoping to work on is to implement very efficient algorithms for computing first the Hermite normal form of a matrix, but later other related special forms of matrices such as the Smith normal form (used heavily in the theory of finitely generated abelian groups). There are a lot of interesting algorithms out there so this should be really fun to work on. Also I quite like the fact I should be able to see the results of implementing efficient algorithms for the HNF first hand as I use them both directly and indirectly (through other algorithms) fairly regularly when computing with all sorts of objects. I’m planning to start of implementing a couple of the more basic HNF algorithms to get a feel for the project and get the relevant helper functions implemented, before moving on to more complicated methods such as Pernet and Stein’s algorithm or Pauderis and Storjohann after that I’ll try and move on to the Smith and possibly Howell normal forms. If I am accepted I’ll continue blogging here weekly about my progress thinking about and implementing these algorithms (possibly more often if I have more to say!).