Random Krylov spaces over finite fields

Richard P. Brent*, Shuhong Gao, Alan G.B. Lauder

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

31 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)276-287
Number of pages12
JournalSIAM Journal on Discrete Mathematics
Volume16
Issue number2
DOIs
Publication statusPublished - Feb 2003
Externally publishedYes

Fingerprint

Dive into the research topics of 'Random Krylov spaces over finite fields'. Together they form a unique fingerprint.

Cite this