Computing Krylov iterates in the time of matrix multiplication
Open Access
- 16 July 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 419-428
Abstract
Krylov methods rely on iterated matrix-vector products Akuj for an n × n matrix A and vectors u1, …, um. The space spanned by all iterates Akuj admits a particular basis — the maximal Krylov basis — which consists of iterates of the first vector u1, Au1, A2u1, …, 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 Math 1 comes from repeated squarings of A and logarithmically many Gaussian eliminations. Here ω > 2 is a feasible exponent for matrix multiplication over the base field. We present an algorithm computing the maximal Krylov basis in Math 2 field operations when Math 3, and even Math 4 as soon as Math 5 for some fixed real c > 0. As a consequence, we show that the Frobenius normal form together with a transformation matrix can be computed deterministically in Math 6, and therefore matrix exponentiation Ak can be performed in the latter complexity if Math 7 for some fixed ε > 0. A key idea for these improvements is to rely on fast algorithms for m × m polynomial matrices of average degree n/m, involving high-order lifting and minimal kernel bases.Keywords
All Related Versions
Funding Information
- ANR (JCJC CREAM)
This publication has 22 references indexed in Scilit:
- Deterministic computation of the characteristic polynomial in the time of matrix multiplicationJournal of Complexity, 2021
- Computing minimal interpolation basesJournal of Symbolic Computation, 2017
- Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrixJournal of Complexity, 2017
- A deterministic algorithm for inverting a polynomial matrixJournal of Complexity, 2015
- Triangular -basis decompositions and derandomization of linear algebra algorithms overJournal of Symbolic Computation, 2012
- Normal forms for general polynomial matricesJournal of Symbolic Computation, 2006
- Algebra2002
- Fast Parallel Algorithms for Matrix Reduction to Normal FormsApplicable Algebra in Engineering, Communication and Computing, 1997
- Fast algorithms for the characteristics polynomialTheoretical Computer Science, 1985
- Approximate algorithms to derive exact solutions to systems of linear equations1979