1. Fast Algorithms for Discrete Differential Equations
- Author
-
Bostan, Alin, Notarantonio, Hadrien, Safey El Din, Mohab, 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), ANR-19-CE40-0018,DeRerumNatura,Décider l'irrationalité et la transcendance(2019), ANR-19-CE48-0015,ECARP,Algorithmes efficaces et exacts pour la planification de trajectoire en robotique(2019), ANR-22-CE91-0007,EAGLES,Algorithmes Efficaces pour Guessing, Inégalités, Sommation(2022), European Project: 813211,H2020-EU.1.3. - EXCELLENT SCIENCE - Marie Skłodowska-Curie Actions (Main Programme), and H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)
- Subjects
FOS: Computer and information sciences ,[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] ,Computer Science - Symbolic Computation ,Algebraic functions ,Functional equations ,Discrete differential equations ,Complexity ,Symbolic Computation (cs.SC) ,[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] ,Mathematics - Algebraic Geometry ,Catalytic variables ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Algebraic Geometry (math.AG) ,Algorithms - Abstract
Discrete Differential Equations (DDEs) are functional equations that relate polynomially a power series $F(t,u)$ in $t$ with polynomial coefficients in a "catalytic" variable $u$ and the specializations, say at $u=1$, of $F(t,u)$ and of some of its partial derivatives in $u$. DDEs occur frequently in combinatorics, especially in map enumeration. If a DDE is of fixed-point type then its solution $F(t,u)$ is unique, and a general result by Popescu (1986) implies that $F(t,u)$ is an algebraic power series. Constructive proofs of algebraicity for solutions of fixed-point type DDEs were proposed by Bousquet-M\'elou and Jehanne (2006). Bostan et. al (2022) initiated a systematic algorithmic study of such DDEs of order 1. We generalize this study to DDEs of arbitrary order. First, we propose nontrivial extensions of algorithms based on polynomial elimination and on the guess-and-prove paradigm. Second, we design two brand-new algorithms that exploit the special structure of the underlying polynomial systems. Last, but not least, we report on implementations that are able to solve highly challenging DDEs with a combinatorial origin., Comment: 11 pages, revised version
- Published
- 2023