Block Wiedemann algorithm

The block Wiedemann algorithm for computing kernel vectors of a matrix over a finite field is a generalisation by Don Coppersmith of an algorithm due to Doug Wiedemann.
Wiedemann's algorithm.
Let formula_1 be an formula_2 square matrix over some finite field F, let formula_3 be a random vector of length formula_4, and let formula_5. Consider the sequence of vectors formula_6 obtained by repeatedly multiplying the vector by the matrix formula_1; let formula_8 be any other vector of length formula_4, and consider the sequence of finite-field elements formula_10
We know that the matrix formula_1 has a minimal polynomial; by the Cayley–Hamilton theorem we know that this polynomial is of degree (which we will call formula_12) no more than formula_4. Say formula_14. Then formula_15; so the minimal polynomial of the matrix annihilates the sequence formula_16 and hence formula_17.
But the Berlekamp–Massey algorithm allows us to calculate relatively efficiently some sequence formula_18 with formula_19. Our hope is that this sequence, which by construction annihilates formula_20, actually annihilates formula_16; so we have formula_22. We then take advantage of the initial definition of formula_23 to say formula_24 and so formula_25 is a hopefully non-zero kernel vector of formula_1.
The block Wiedemann (or Coppersmith-Wiedemann) algorithm.
The natural implementation of sparse matrix arithmetic on a computer makes it easy to compute the sequence "S" in parallel for a number of vectors equal to the width of a machine word – indeed, it will normally take no longer to compute for that many vectors than for one. If you have several processors, you can compute the sequence S for a different set of random vectors in parallel on all the computers.
It turns out, by a generalization of the Berlekamp–Massey algorithm to provide a sequence of small matrices, that you can take the sequence produced for a large number of vectors and generate a kernel vector of the original large matrix. You need to compute formula_27 for some formula_28 where formula_29 need to satisfy formula_30 and formula_31 are a series of vectors of length n; but in practice you can take formula_31 as a sequence of unit vectors and simply write out the first formula_33 entries in your vectors at each time "t".
References.
Wiedemann, D., "Solving sparse linear equations over finite fields," IEEE Trans. Inf. Theory IT-32, pp. 54-62, 1986.
D. Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Math. Comp. 62 (1994), 333-350.
Villard's 1997 research report 'A study of Coppersmith's block Wiedemann algorithm using matrix polynomials' (the cover material is in French but the content in English) is a reasonable description.
Thomé's paper 'Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm' uses a more sophisticated FFT-based algorithm for computing the vector generating polynomials, and describes a practical implementation with "i"max = "j"max = 4 used to compute a kernel vector of a 484603×484603 matrix of entries modulo 2607−1, and hence to compute discrete logarithms in the field "GF"(2607).