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$...
Main Authors: | , , |
---|---|
Other Authors: | , , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2023
|
Subjects: | |
Online Access: | https://inria.hal.science/hal-03979664 https://inria.hal.science/hal-03979664v2/document https://inria.hal.science/hal-03979664v2/file/BoNeYu23.pdf |
id |
ftccsdartic:oai:HAL:hal-03979664v2 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-03979664v2 2023-11-05T03:45:23+01:00 Beating binary powering for polynomial matrices Bostan, Alin Neiger, Vincent Yurkevich, Sergey 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) Tromso, Norway 2023-07-24 https://inria.hal.science/hal-03979664 https://inria.hal.science/hal-03979664v2/document https://inria.hal.science/hal-03979664v2/file/BoNeYu23.pdf en eng HAL CCSD hal-03979664 https://inria.hal.science/hal-03979664 https://inria.hal.science/hal-03979664v2/document https://inria.hal.science/hal-03979664v2/file/BoNeYu23.pdf http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation https://inria.hal.science/hal-03979664 ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromso, Norway https://www.issac-conference.org/2023/ Algebraic Algorithms Computational Complexity Binary Powering C-recursive Sequence Rational Power Series Linear Differential Equations Creative Telescoping Polynomial Matrices [INFO]Computer Science [cs] info:eu-repo/semantics/conferenceObject Conference papers 2023 ftccsdartic 2023-10-07T22:34:14Z 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. Conference Object Tromso Tromso Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
Algebraic Algorithms Computational Complexity Binary Powering C-recursive Sequence Rational Power Series Linear Differential Equations Creative Telescoping Polynomial Matrices [INFO]Computer Science [cs] |
spellingShingle |
Algebraic Algorithms Computational Complexity Binary Powering C-recursive Sequence Rational Power Series Linear Differential Equations Creative Telescoping Polynomial Matrices [INFO]Computer Science [cs] Bostan, Alin Neiger, Vincent Yurkevich, Sergey Beating binary powering for polynomial matrices |
topic_facet |
Algebraic Algorithms Computational Complexity Binary Powering C-recursive Sequence Rational Power Series Linear Differential Equations Creative Telescoping Polynomial Matrices [INFO]Computer Science [cs] |
description |
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. |
author2 |
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 |
author |
Bostan, Alin Neiger, Vincent Yurkevich, Sergey |
author_facet |
Bostan, Alin Neiger, Vincent Yurkevich, Sergey |
author_sort |
Bostan, Alin |
title |
Beating binary powering for polynomial matrices |
title_short |
Beating binary powering for polynomial matrices |
title_full |
Beating binary powering for polynomial matrices |
title_fullStr |
Beating binary powering for polynomial matrices |
title_full_unstemmed |
Beating binary powering for polynomial matrices |
title_sort |
beating binary powering for polynomial matrices |
publisher |
HAL CCSD |
publishDate |
2023 |
url |
https://inria.hal.science/hal-03979664 https://inria.hal.science/hal-03979664v2/document https://inria.hal.science/hal-03979664v2/file/BoNeYu23.pdf |
op_coverage |
Tromso, Norway |
genre |
Tromso Tromso |
genre_facet |
Tromso Tromso |
op_source |
ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation https://inria.hal.science/hal-03979664 ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromso, Norway https://www.issac-conference.org/2023/ |
op_relation |
hal-03979664 https://inria.hal.science/hal-03979664 https://inria.hal.science/hal-03979664v2/document https://inria.hal.science/hal-03979664v2/file/BoNeYu23.pdf |
op_rights |
http://creativecommons.org/licenses/by/ info:eu-repo/semantics/OpenAccess |
_version_ |
1781707470472740864 |