Beating binary powering for polynomial matrices

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$...

Full description

Bibliographic Details
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, 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
Description
Summary: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.

Similar Items