Random Krylov spaces over finite fields

被引：25

作者：

Brent, RP ^{[1
]}

Gao, SH

Lauder, AGB

机构：

[1] Univ Oxford, Comp Lab, Oxford OX1 3QD, England

[2] Clemson Univ, Dept Math Sci, Clemson, SC 29634 USA

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2003年 / 16卷 / 02期

关键词：

finite field; vector space; linear transformation; Krylov subspace;

D O I：

10.1137/S089548010139388X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：276 / 287

页数：12

共 16 条

[1]

ADKINS WA, 1992, GRAD TEXTS MATH, V136

[2] DETERMINANTS AND RANKS OF RANDOM MATRICES OVER ZM [J].