Sparse LU Factorization modulo p: an update.

In this talk, I will consider elimination methods for computing the rank of sparse rectangular matrices over a finite field. The idea is to find first a large set of pivots without any arithmetical operation, that would enable us to reduce the number of elimination steps. After some reminders about sparse LU factorisation, I will introduce a new algorithm inspired by the GPLU algorithm, and by a pivot selection heuristic used for the treatment of matrices that come from Gröbner basis computation. Then, I will explain how we improved this heuristic so that we could find a larger set of pivots without any arithmetical operation. Finally, I will briefly present our implementation. Our benchmarks show that it can compute in five minutes the rank of sparse matrices that previously required more than 15 days.
This talk is based on the following article: http://cristal.univ-lille.fr/~bouillag/pub/CASC16.pdf, as well as our further work.