imported>OAbot: Open access bot: arxiv added to citation with #oabot.

2023-08-13T19:37:53Z

Open access bot: arxiv added to citation with #oabot.

New page

The '''block Wiedemann algorithm''' for computing [[kernel (linear algebra)|kernel]] [[vector space|vectors]] of a [[matrix (mathematics)|matrix]] over a [[finite field]] is a generalization by [[Don Coppersmith]] of an algorithm due to Doug Wiedemann.

== Wiedemann's algorithm ==

Let <math>M</math> be an <math>n\times n</math> [[square matrix]] over some [[finite field]] F, let <math>x_{\mathrm {base}}</math> be a random vector of length <math>n</math>, and let <math>x = M x_{\mathrm {base}}</math>. Consider the sequence of vectors <math>S = \left[x, Mx, M^2x, \ldots\right]</math> obtained by repeatedly multiplying the vector by the matrix <math>M</math>; let <math>y</math> be any other vector of length <math>n</math>, and consider the sequence of finite-field elements <math>S_y = \left[y \cdot x, y \cdot Mx, y \cdot M^2x \ldots\right]</math>

We know that the matrix <math>M</math> has a [[Minimal polynomial (linear algebra)|minimal polynomial]]; by the [[Cayley–Hamilton theorem]] we know that this polynomial is of degree (which we will call <math>n_0</math>) no more than <math>n</math>. Say <math>\sum_{r=0}^{n_0} p_rM^r = 0</math>. Then <math>\sum_{r=0}^{n_0} y \cdot (p_r (M^r x)) = 0</math>; so the minimal polynomial of the matrix annihilates the sequence <math>S</math> and hence <math>S_y</math>.

But the [[Berlekamp–Massey algorithm]] allows us to calculate relatively efficiently some sequence <math>q_0 \ldots q_L</math> with <math>\sum_{i=0}^L q_i S_y[{i+r}]=0 \;\forall \; r</math>. Our hope is that this sequence, which by construction annihilates <math>y \cdot S</math>, actually annihilates <math>S</math>; so we have <math>\sum_{i=0}^L q_i M^i x = 0</math>. We then take advantage of the initial definition of <math>x</math> to say <math>M \sum_{i=0}^L q_i M^i x_{\mathrm {base}} = 0</math> and so <math>\sum_{i=0}^L q_i M^i x_{\mathrm {base}}</math> is a hopefully non-zero kernel vector of <math>M</math>.

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

== Invariant Factor Calculation ==
The block Wiedemann algorithm can be used to calculate the leading [[invariant factor]]s of the matrix, ie, the largest blocks of the [[Frobenius normal form]]. Given <math>M \in F_q^{n \times n}</math> and <math>U, V \in F_q^{b \times n}</math> where <math>F_q</math> is a finite field of size <math>q</math>, the probability <math>p</math> that the leading <math>k < b</math> invariant factors of <math>M</math> are preserved in <math>\sum_{i=0}^{2n-1}UM^iV^T x^i</math> is

<div class="center">
<math>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}</math>.<ref>{{Cite journal |last=Harrison |first=Gavin |last2=Johnson |first2=Jeremy |last3=Saunders |first3=B. David |date=2022-01-01 |title=Probabilistic analysis of block Wiedemann for leading invariant factors |url=https://www.sciencedirect.com/science/article/pii/S0747717121000419 |journal=Journal of Symbolic Computation |language=en |volume=108 |pages=98–116 |doi=10.1016/j.jsc.2021.06.005 |issn=0747-7171|arxiv=1803.03864 }}</ref>
</div>

== References ==
{{Reflist}}

* 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 '[http://citeseer.ist.psu.edu/cache/papers/cs/4204/ftp:zSzzSzftp.imag.frzSzpubzSzCALCUL_FORMELzSzRAPPORTzSz1997zSzRR975.pdf 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 '[http://hal.archives-ouvertes.fr/docs/00/10/34/17/PDF/jsc.pdf Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm]' uses a more sophisticated [[Fast Fourier transform|FFT]]-based algorithm for computing the vector generating polynomials, and describes a practical implementation with ''i''<sub>max</sub> = ''j''<sub>max</sub> = 4 used to compute a kernel vector of a 484603×484603 matrix of entries modulo 2<sup>607</sup>−1, and hence to compute discrete logarithms in the field ''GF''(2<sup>607</sup>).

{{Numerical linear algebra}}

[[Category:Numerical linear algebra]]

Block Wiedemann algorithm - Revision history

imported>OAbot: Open access bot: arxiv added to citation with #oabot.