Fast Algorithms for Discrete Differential Equations

• Main Authors: Bostan, Alin, Notarantonio, Hadrien, Safey El Din, Mohab
• 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), 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), H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019)
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2023
• Subjects: Functional equations; Discrete differential equations; Algorithms; Complexity; Catalytic variables; Algebraic functions; [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]; [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]; [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]; [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]; Tromso
• Online Access: https://inria.hal.science/hal-03978089; https://inria.hal.science/hal-03978089v2/document; https://inria.hal.science/hal-03978089v2/file/reviewed_BoNoSa2023--HAL-ARXIV.pdf

International audience Discrete Differential Equations (DDEs) are functional equationsthat relate algebraically a power series F (t, u) in t with polynomialcoefficients in a “catalytic” variable u and the specializations, sayat u = 1, of F (t, u) and of some of its partial derivatives in u. DDEsoccur frequently in combinatorics, especially in map enumeration.If a DDE is of fixed-point type then its solution F (t, u) is unique, anda general result by Popescu (1986) implies that F (t, u) is an algebraicpower series. Constructive proofs of algebraicity for solutions offixed-point type DDEs were proposed in 2006 by Bousquet-Mélouand Jehanne. Last year, Bostan et al. initiated a systematic algo-rithmic study of such DDEs of order 1. We generalize this study toDDEs of arbitrary order. First, we propose nontrivial extensions ofalgorithms based on polynomial elimination and on the guess-and-prove paradigm. Second, we design two brand-new algorithms thatexploit the special structure of the underlying polynomial systems.Last, but not least, we report on implementations that are able tosolve highly challenging DDEs with a combinatorial origin.