Random Krylov spaces over finite fields
201. R. P. Brent,
S. Gao and
A. G. B. Lauder,
Random Krylov spaces over finite fields,
SIAM Journal on Discrete Mathematics 16 (2003), 276-287.
MR 1 982 139.
Preprint:
dvi (25K),
pdf (161K),
ps (84K).
Abstract
Motivated by a connection with block iterative methods for solving
linear systems over finite fields, we consider the probability
that the Krylov space generated by a fixed linear mapping and
a random set of elements in a vector space over a finite field
equals the space itself. We obtain an exact formula for this probability,
and from it we derive good lower bounds that approach 1
exponentially fast as the size of the set increases.
Comments
The problem is relevant to Krylov subspace methods for solving large
sparse linear systems over finite fields. Such systems arise, for example,
in the MPQS and NFS methods for integer factorisation
[196].
The methods of
[94] are relevant to the proof of Lemma 4.
Go to next publication
Return to Richard Brent's index page