Block Wiedemann algorithm

The Block Wiedemann algorithm for computing the nullspace of a matrix over a finite field is a generalisation of an algorithm due to Don Coppersmith.

Coppersmith's algorithm

Let M be an nxn square matrix over some finite field F, and let x be a random vector of length n. Consider the sequence $S=\left[x,Mx,M^{2}x,\ldots \right]$ obtained by repeatedly multiplying the vector by the matrix M; let y be any other vector of length n, and consider the sequence of finite-field elements y.x, y.Mx, y.M^2x ...

We know that the matrix M has a minimal polynomial; by the Cayley-Hamilton Theorem we know that this polynomial is of degree (which we will call $n_{0}$) no more than n. Say $\sum _{r=0}^{n_{0}}p_{r}M^{r}=0$. Then $\sum _{r=0}^{n_{0}}y\cdot (p_{r}(M^{r}x))=0$; so the minimal polynomial of the matrix annihilates the sequence S.

But the Berlekamp-Massey algorithm allows us to calculate relatively efficiently some polynomial with $\sum _{i=0}^{m}q_{i}S_{i+r}=0\forall r$.

== The Block 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 generalisation 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 $y_{i}\cdot M^{t}x_{j}$ for some $i=0\ldots i_{\max },j=0\ldots j_{\max },t=0\ldots t_{\max }$ where $i_{\max },j_{\max },t_{\max }$ need to satisfy $t_{\max }>{\frac {d}{i_{\max }}}+{\frac {d}{j_{\max }}}+O(1)$ and $y_{i}$ are a series of vectors of length n; but in practice you can take $y_{i}$ as a sequence of unit vectors and simply write out the first $i_{\max }$ entries in your vectors at each time t.