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.