A Direttissimo Algorithm for Equidimensional Decomposition

• Main Authors: Eder, Christian, Lairez, Pierre, Mohr, Rafael, Safey El Din, Mohab
• Other Authors: RPTU Kaiserslautern-Landau, 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), EOARD-AFOSR grant FA8665-20-1-7029, DFG Sonderforschungsbereich TRR 195, Forschungsinitiative Rheinland-Pfalz, ANR-18-CE33-0011,SESAME,Singularités Et Stabilité des AsservisseMEnts référencés capteurs(2018), 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: 101040794,10000 DIGITS
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2023
• Subjects: [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC]; Tromsø
• Online Access: https://hal.science/hal-04000248; https://hal.science/hal-04000248v2/document; https://hal.science/hal-04000248v2/file/arxiv_version.pdf

International audience We describe a recursive algorithm that decomposes an algebraic set into locally closed equidimensional sets, i.e. sets which each have irreducible components of the same dimension. At the core of this algorithm, we combine ideas from the theory of triangular sets, a.k.a. regular chains, with Gröbner bases to encode and work with locally closed algebraic sets. Equipped with this, our algorithm avoids projections of the algebraic sets that are decomposed and certain genericity assumptions frequently made when decomposing polynomial systems, such as assumptions about Noether position. This makes it produce fine decompositions on more structured systems where ensuring genericity assumptions often destroys the structure of the system at hand. Practical experiments demonstrate its efficiency compared to state-of-the-art implementations.