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
相关论文
共 50 条
12345