Jump to content

Block Wiedemann algorithm

From Wikipedia, the free encyclopedia

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

[edit]

Let be an square matrix over some finite field F, let be a random vector of length , and let . Consider the sequence of vectors obtained by repeatedly multiplying the vector by the matrix ; let be any other vector of length , and consider the sequence of finite-field elements

We know that the matrix has a minimal polynomial; by the Cayley–Hamilton theorem we know that this polynomial is of degree (which we will call ) no more than . Say . Then ; so the minimal polynomial of the matrix annihilates the sequence and hence .

But the Berlekamp–Massey algorithm allows us to calculate relatively efficiently some sequence with . Our hope is that this sequence, which by construction annihilates , actually annihilates ; so we have . We then take advantage of the initial definition of to say and so is a hopefully non-zero kernel vector of .

The block Wiedemann (or Coppersmith-Wiedemann) algorithm

[edit]

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 for some where need to satisfy and are a series of vectors of length n; but in practice you can take as a sequence of unit vectors and simply write out the first entries in your vectors at each time t.

Invariant Factor Calculation

[edit]

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 and where is a finite field of size , the probability that the leading invariant factors of are preserved in is

.[1]

References

[edit]
  1. ^ Harrison, Gavin; Johnson, Jeremy; Saunders, B. David (2022-01-01). "Probabilistic analysis of block Wiedemann for leading invariant factors". Journal of Symbolic Computation. 108: 98–116. arXiv:1803.03864. doi:10.1016/j.jsc.2021.06.005. ISSN 0747-7171.
  • 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.