Beating binary powering for polynomial matrices

• Main Authors: Bostan, Alin, Neiger, Vincent, Yurkevich, Sergey
• Other Authors: Calcul formel, mathématiques expérimentales et interactions (MATHEXP), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Universität Wien = University of Vienna, The third author was supported by the ÖAW DOC fellowship P-26101, ANR-22-CE91-0007,EAGLES,Algorithmes Efficaces pour Guessing, Inégalités, Sommation(2022), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019)
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2023
• Subjects: Algebraic Algorithms; Computational Complexity; Binary Powering; C-recursive Sequence; Rational Power Series; Linear Differential Equations; Creative Telescoping; Polynomial Matrices; [INFO]Computer Science [cs]; Tromso
• Online Access: https://inria.hal.science/hal-03979664; https://inria.hal.science/hal-03979664v2/document; https://inria.hal.science/hal-03979664v2/file/BoNeYu23.pdf

International audience The $N$th power of a polynomial matrix of fixed size and degree can be computed by binary powering as fast as multiplying two polynomials of linear degree in $N$. When Fast Fourier Transform (FFT) is available, the resulting arithmetic complexity is \emph{softly linear} in $N$, i.e. linear in $N$ with extra logarithmic factors. We show that it is possible to beat binary powering, by an algorithm whose complexity is \emph{purely linear} in $N$, even in absence of FFT. The key result making this improvement possible is that the entries of the $N$th power of a polynomial matrix satisfy linear differential equations with polynomial coefficients whose orders and degrees are independent of $N$. Similar algorithms are proposed for two related problems: computing the $N$th term of a C-recursive sequence of polynomials, and modular exponentiation to the power $N$ for bivariate polynomials.