Week of 5/26 Update

This week mentor and Linbox contributor Brice Boyer from NCSU came to deliver 2 talks on computational linear algebra. While he was here we discussed how to implement benchmarking in Linbox. There are currently two classes that handle benchmarking: one extensive plotting and data-recording class that Brice wrote, and a simplistic CSV serializer that I wrote. We decided that the best thing to do would be to combine the two classes so there's one consistent interface for all benchmarking in Linbox. This will be important later once the parallel code is written and tuning can begin.

I've been working on getting a sequential version of the code needed to compute the matrix min-poly up and working. In theory this should be trivial, since there are two sequential implementation of the Block-Wiedemann algorithm already in Linbox. Unfortunately, it seems there are some bugs in George Yuhasz's version (described in his thesis here) and it was failing to work for small fields, such as GF(3). Right now I'm trying to track down the bug that's causing this. There's another implementation of Block-Wiedemann, the sigma-basis code, that I've still yet to look at in any great detail. At the same time I've been working on a reference implementation of Block-Wiedemann of my own, written in Python. My hope is that I can use it to test and debug the results of the two efficient version already in Linbox.

Although my original plan was to focus solely on Block-Wiedemann, Prof. Saunders raised another option for parallelism. In the scalar Wiedemann algorithm computations are done over an extension field GF(q^n) to solve a matrix over the base field GF(q). The computations in GF(q^n) are potentially very easily parallelizable. With this in mind, my hope is that I can improve the existing mechanism for generating extension fields, and then perform those operations in parallel. Ideally I'll be able to compare these results to those from Block-Wiedemann, but it may end up being more of a backup plan if the Block-Wiedemann solvers turn out to be more buggy than expected.