Fast Algorithms for Discrete Differential Equations
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. DDEsoccu...
Main Authors: | , , |
---|---|
Other Authors: | , , , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2023
|
Subjects: | |
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 |
Summary: | 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. |
---|