GSoC with Flint - Week 5

Week 5 of my GSoC project is now over and this week I've been trying some variations of the older approaches to computing the Hermite normal form that I implemented in the first few weeks, I've had some success extending the Kannan-Bachem approach to non-square matrices and implementing other practical speed-ups. However my main project for this week, working on a variant of the modular approach for use when factors of the determinant are known, hasn't worked out so well yet. I've been really struggling to make it work as intended and have decided to place this to the side for the moment and come back to it later as it is not vital to the rest of the project. The main use case would be if the determinant was larger than word sized but a factorisation into relatively prime factors all was known where each factor fits in a word, here there would probably be an advantage to using multiple matrices modulo these factors. If however one of the factors was larger than word size or indeed the determinant itself fits in a single word I can't see how using such a factorisation would help much (if at all), there is also the problem of obtaining the factors in the first place, certainly some methods of computing the determinant (such as the method described by Abbot, Bronstein and Mulders) can give some factors of the determinant for free when computing it but this is certainly not guaranteed to give us useful information in light of the above. Nevertheless I would like to try and finish implementing this at some point, but don't want to slow the whole project down just working on this.

Next week I'll begin working on the algorithm given by Pernet and Stein which will take some time to do right and so I expect to be working on this in some way or another for the whole week (at least!). Initially I'll get a simplified version working (which will likely end up looking like the algorithm of Micciancio and Warinschi) and then I'll start working on the improvements suggested in Pernet and Stein's paper. Hopefully when this is done it will be extremely fast compared to the algorithms I have worked on so far, however it's run time will depend on what I can squeeze out of the modular approach I worked on a couple of weeks ago.

GSoC with Flint - Week 4

This week I've been working more on some of the older approaches to computing the HNF. First I finished off the modulo determinant method which works well for square matrices of full rank. One of the issues with this method however is that the determinant needs to be calculated first and can be quite large, in which case there may be little gained by calculating modulo it.

I've also implemented the algorithm described by Kannan and Bachem which takes the principal minors to Hermite form one at a time, as opposed to other methods I've implemented so far which work column by column. This also provides significant improvement on the classical method, and indeed is performing better than the modular approach in many cases.

For the next week I'll be trying to optimise the algorithms implemented so far as much as possible, especially the modular approach of Domich, Kannan and Trotter as this plays a key role in the algorithm of Pernet and Stein. One thing I would like to try is combining the two approaches I worked on this week and making a modulo determinant version of the Kannan-Bachem algorithm. There is also the possibility that factoring the determinant into some relatively prime parts and working modulo each of those, before recombining at the end with the Chinese remainder theorem, of course this involves factoring the determinant which could make the whole procedure less worthwhile. I also need to make the necessary modifications to ensure that all algorithms work in the non-square case as efficiently as possible.

GSoC with Flint - Week 3

This week I've been able to get started working on my GSoC project full time after finishing my university exams on Tuesday (hooray!).

I finished off what I was working on at the time of the last update, a more efficient algorithm that still computes the Hermite normal form in a straightforward way but takes less time by using the extended Euclidean algorithm to reduce rows rather than simply repeatedly reducing one row using another. The coefficients can still grow very fast in this algorithm which leaves it highly non-optimal in practice however small changes can be made to reduce this problem such as changing the order in which rows are reduced (this is described by Bradley here).

One way to mitigate the coefficient explosion problem is to perform the computations modulo some number and then use the result of this computation to find the actual HNF. If we use a multiple of the determinant of the HNF matrix we are trying to find (which we can in fact determine from the original matrix) the real HNF can be found fairly easily and this is what I have been working on for the past couple of days. This method of finding the HNF is due to Domich, Kannan and Trotter and the paper describing it can be found here. The function I have implemented seems to be working fine on the test cases it is given but I am getting some memory leaks that I'm really having trouble getting to the bottom of which is my main problem currently.

Once this is done I'll start working on a multimodular algorithm which will involve computing the HNF modulo several primes and combining the resulting matrices via the Chinese remainder theorem.

GSoC with Flint - Week 2

I've just reached the end of the second week of Google summer of code so it's about time for a short update.

As with last week I've been working on the project in between my exams (which finish on Tuesday!) so progress has been slow so far. This week I got a few bugs fixed with the classical implementation and test code before moving on to starting work on another algorithm for for finding the Hermite normal form based on the extended Euclidean algorithm. This is still a classical algorithm but it does improve the efficiency of the most basic approach. However it still suffers from the coefficient expansion problem that causes these algorithms to all end up taking more time than they might initially appear to, which is why more intricate methods are needed for algorithms that scale well.

I'm very much looking forward to getting started working on Flint full time this week and hopefully next week I'll have some more interesting news to share here!

GSoC with Flint - Week 1

My Google summer of code project was accepted, so this summer I'm working on implementing efficient methods to find the Hermite normal form of a matrix in Flint. The official coding period began this week and so I have been starting to code.

It has been a slow first week for me as I still have several university exams on, so I haven't had as much time to work on the project this week as I will in future weeks. So there is not much to report so far but I'll do so anyway to get in to the swing of things.

I originally wrote some sample code when I applied for GSoC which was a very simple HNF algorithm following Henri Cohen's book. This used a column Hermite normal form convention that placed zero columns at the start, however this is not the convention I am using for the actual project where the row Hermite form makes more sense (additionally this convention is used by two of the papers I am trying to implement). So I have been changing the code and tests over to the new convention. This has not been quite as straightforward as I would have liked and it has thrown up a few bugs, seemingly in my test code rather than in the HNF algorithm itself however. Hopefully I can sort these testing issues out and get onto implementing some more interesting algorithms soon.

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 $q$-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 $q$-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!).

Tomorrow's mathematicians today 2014

Last weekend I went to Tomorrow's Mathematicians Today 2014, a conference for undergraduates, this year at the university of Surrey. This was the third time the event has taken place but only the second time consecutively, hopefully it will continue to be a yearly event (I did hear a rumour it will be running next year which I really hope is true). I had a good time once again, in fact the whole event was very similar to the year before, but more relaxing for me personally as I did not give a talk this year.
The attendance seemed very much the same as previously, which was a little surprising seeing as more people from Warwick came this year, maybe the weather affected attendance badly?

The talks were a nice variety again and I saw a lot of cool things, most notably the keynote speaker Professor Luis Alday's talk on some of the mathematics of string theory and the well deserved GCHQ prize winner M. Syafiq Johar's talk on Rational tangles and the Euclidean algorithm. There were also interesting presentations on parallel algorithms and modularity.

I would highly recommend any UK undergraduate to consider attending such a conference (put a note in your calendar to Google for it sometime next October), and moreover to consider presenting a talk or a poster. In fact I almost wish I had prepared a talk now!

Riemann hypotheses

Must... start... writing... regularly, this is just a quick update about a talk I gave recently to try and ease myself into the swing of things.

I recently prepared a talk for the Warwick maths society on some analogues of the Riemann zeta function and associated statements about them that resemble the Riemann hypothesis. The talk was called "Riemann hypotheses", and there are some slides here.
It was a lot of fun to prepare and even though I only had time to discuss the Riemann, Ihara and Dedekind zeta functions in the end I think my message of "zeta functions are cool and varied objects that are fun to play with" came across at least a little bit.