Random Krylov spaces over finite fields

Richard P. Brent; Shuhong Gao; Alan G.B. Lauder

doi:10.1137/S089548010139388X

Random Krylov spaces over finite fields

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

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	276-287
Number of pages	12
Journal	SIAM Journal on Discrete Mathematics
Volume	16
Issue number	2
DOIs	https://doi.org/10.1137/S089548010139388X
Publication status	Published - Feb 2003
Externally published	Yes

Access to Document

10.1137/S089548010139388X

Cite this

@article{e26324a9e9ff45b3b9a0e5326553c09d,

title = "Random Krylov spaces over finite fields",

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.",

keywords = "Finite field, Krylov subspace, Linear transformation, Vector space",

author = "Brent, \{Richard P.\} and Shuhong Gao and Lauder, \{Alan G.B.\}",

year = "2003",

month = feb,

doi = "10.1137/S089548010139388X",

language = "English",

volume = "16",

pages = "276--287",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Random Krylov spaces over finite fields

AU - Brent, Richard P.

AU - Gao, Shuhong

AU - Lauder, Alan G.B.

PY - 2003/2

Y1 - 2003/2

N2 - 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.

AB - 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.

KW - Finite field

KW - Krylov subspace

KW - Linear transformation

KW - Vector space

UR - http://www.scopus.com/inward/record.url?scp=0038137157&partnerID=8YFLogxK

U2 - 10.1137/S089548010139388X

DO - 10.1137/S089548010139388X

M3 - Article

SN - 0895-4801

VL - 16

SP - 276

EP - 287

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

Random Krylov spaces over finite fields

Abstract

Access to Document

Other files and links

Fingerprint

Cite this