# Block Wiedemann algorithm

The block Wiedemann algorithm for computing kernel vectors of a matrix over a finite field is a generalization by Don Coppersmith of an algorithm due to Doug Wiedemann.

## Wiedemann's algorithm

Let $M$ be an $n\times n$ square matrix over some finite field F, let $x_{\mathrm {base} }$ be a random vector of length $n$, and let $x=Mx_{\mathrm {base} }$. Consider the sequence of vectors $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 $S_{y}=\left[y\cdot x,y\cdot Mx,y\cdot M^{2}x\ldots \right]$
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$ and hence $S_{y}$.
But the Berlekamp–Massey algorithm allows us to calculate relatively efficiently some sequence $q_{0}\ldots q_{L}$ with $\sum _{i=0}^{L}q_{i}S_{y}[{i+r}]=0\;\forall \;r$. Our hope is that this sequence, which by construction annihilates $y\cdot S$, actually annihilates $S$; so we have $\sum _{i=0}^{L}q_{i}M^{i}x=0$. We then take advantage of the initial definition of $x$ to say $M\sum _{i=0}^{L}q_{i}M^{i}x_{\mathrm {base} }=0$ and so $\sum _{i=0}^{L}q_{i}M^{i}x_{\mathrm {base} }$ is a hopefully non-zero kernel vector of $M$.

## 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 $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.

## Invariant Factor Calculation

The block Wiedemann algorithm can be used to calculate the leading invariant factors of the matrix, ie, the largest blocks of the Frobenius normal form. Given $M\in F_{q}^{n\times n}$ and $U,V\in F_{q}^{b\times n}$ where $F_{q}$ is a finite field of size $q$, the probability $p$ that the leading $k<b$ invariant factors of $M$ are preserved in $\sum _{i=0}^{2n-1}UM^{i}V^{T}x^{i}$ is
$p\geq {\begin{cases}1/64,&{\text{if }}b=k+1{\text{ and }}q=2\\\left(1-{\frac {3}{2^{b-k}}}\right)^{2}\geq 1/16&{\text{if }}b\geq k+2{\text{ and }}q=2\\\left(1-{\frac {2}{q^{b-k}}}\right)^{2}\geq 1/9&{\text{if }}b\geq k+1{\text{ and }}q>2\end{cases}}$.