Computing Krylov iterates in the time of matrix multiplication

Krylov methods rely on iterated matrix-vector products for an × matrix and vectors 1 , . . ., .The space spanned by all iterates admits a particular basis -the maximal Krylov basiswhich consists of iterates of the first vector 1 , 1 , 2 1 , . .., until reaching linear dependency, then iterating similarly the subsequent vectors until a basis is obtained.Finding minimal polynomials and Frobenius normal forms is closely related to computing maximal Krylov bases.The fastest way to produce these bases was, until this paper, Keller-Gehrig's 1985 algorithm whose complexity bound ( log()) comes from repeated squarings of and logarithmically many Gaussian eliminations.Here > 2 is a feasible exponent for matrix multiplication over F. We present an algorithm computing the maximal Krylov basis in ( loglog()) field operations when ∈ (), and even ( ) as soon as ∈ (/log() ) for some fixed real > 0. As a consequence, we show that the Frobenius normal form together with a transformation matrix can be computed deterministically in ( loglog() 2 ), and therefore matrix exponentiation can be performed in the latter complexity if log() ∈ ( -1- ), for > 0. A key idea for these improvements is to rely on fast algorithms for × polynomial matrices of average degree /, involving high-order lifting and minimal kernel bases.