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 |
id |
ftanrparis:oai:HAL:hal-03978089v2 |
---|---|
record_format |
openpolar |
spelling |
ftanrparis:oai:HAL:hal-03978089v2 2024-09-15T18:39:17+00:00 Fast Algorithms for Discrete Differential Equations 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) H2020-EU.1.3.1. - Fostering new skills by means of excellent initial training of researchers ,10.3030/813211,POEMA(2019) Tromso, Norvège, Norway 2023-07-24 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 en eng HAL CCSD info:eu-repo/grantAgreement//813211/EU/Polynomial Optimization, Efficiency through Moments and Algebra/POEMA hal-03978089 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 info:eu-repo/semantics/OpenAccess ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation https://inria.hal.science/hal-03978089 ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromso, Norvège, Norway 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] info:eu-repo/semantics/conferenceObject Conference papers 2023 ftanrparis 2024-07-12T10:52:06Z 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. Conference Object Tromso Tromso Portail HAL-ANR (Agence Nationale de la Recherche) |
institution |
Open Polar |
collection |
Portail HAL-ANR (Agence Nationale de la Recherche) |
op_collection_id |
ftanrparis |
language |
English |
topic |
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] |
spellingShingle |
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] Bostan, Alin Notarantonio, Hadrien Safey El Din, Mohab Fast Algorithms for Discrete Differential Equations |
topic_facet |
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] |
description |
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. |
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) 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 |
author |
Bostan, Alin Notarantonio, Hadrien Safey El Din, Mohab |
author_facet |
Bostan, Alin Notarantonio, Hadrien Safey El Din, Mohab |
author_sort |
Bostan, Alin |
title |
Fast Algorithms for Discrete Differential Equations |
title_short |
Fast Algorithms for Discrete Differential Equations |
title_full |
Fast Algorithms for Discrete Differential Equations |
title_fullStr |
Fast Algorithms for Discrete Differential Equations |
title_full_unstemmed |
Fast Algorithms for Discrete Differential Equations |
title_sort |
fast algorithms for discrete differential equations |
publisher |
HAL CCSD |
publishDate |
2023 |
url |
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 |
op_coverage |
Tromso, Norvège, 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-03978089 ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromso, Norvège, Norway |
op_relation |
info:eu-repo/grantAgreement//813211/EU/Polynomial Optimization, Efficiency through Moments and Algebra/POEMA hal-03978089 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 |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1810483667665944576 |