A Direttissimo Algorithm for Equidimensional Decomposition
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. regul...
Main Authors: | , , , |
---|---|
Other Authors: | , , , , , , , , , , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2023
|
Subjects: | |
Online Access: | https://hal.science/hal-04000248 https://hal.science/hal-04000248v2/document https://hal.science/hal-04000248v2/file/arxiv_version.pdf |
id |
ftccsdartic:oai:HAL:hal-04000248v2 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-04000248v2 2023-11-05T03:45:23+01:00 A Direttissimo Algorithm for Equidimensional Decomposition Eder, Christian Lairez, Pierre Mohr, Rafael Safey El Din, Mohab 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 Tromsø, Norway 2023-07-24 https://hal.science/hal-04000248 https://hal.science/hal-04000248v2/document https://hal.science/hal-04000248v2/file/arxiv_version.pdf en eng HAL CCSD info:eu-repo/grantAgreement//101040794/EU/Transcendental methods in computational nonlinear algebra/10000 DIGITS hal-04000248 https://hal.science/hal-04000248 https://hal.science/hal-04000248v2/document https://hal.science/hal-04000248v2/file/arxiv_version.pdf info:eu-repo/semantics/OpenAccess ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation https://hal.science/hal-04000248 ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromsø, Norway [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC] info:eu-repo/semantics/conferenceObject Conference papers 2023 ftccsdartic 2023-10-07T22:33:42Z 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. Conference Object Tromsø Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
[MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC] |
spellingShingle |
[MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC] Eder, Christian Lairez, Pierre Mohr, Rafael Safey El Din, Mohab A Direttissimo Algorithm for Equidimensional Decomposition |
topic_facet |
[MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC] |
description |
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. |
author2 |
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 |
author |
Eder, Christian Lairez, Pierre Mohr, Rafael Safey El Din, Mohab |
author_facet |
Eder, Christian Lairez, Pierre Mohr, Rafael Safey El Din, Mohab |
author_sort |
Eder, Christian |
title |
A Direttissimo Algorithm for Equidimensional Decomposition |
title_short |
A Direttissimo Algorithm for Equidimensional Decomposition |
title_full |
A Direttissimo Algorithm for Equidimensional Decomposition |
title_fullStr |
A Direttissimo Algorithm for Equidimensional Decomposition |
title_full_unstemmed |
A Direttissimo Algorithm for Equidimensional Decomposition |
title_sort |
direttissimo algorithm for equidimensional decomposition |
publisher |
HAL CCSD |
publishDate |
2023 |
url |
https://hal.science/hal-04000248 https://hal.science/hal-04000248v2/document https://hal.science/hal-04000248v2/file/arxiv_version.pdf |
op_coverage |
Tromsø, Norway |
genre |
Tromsø |
genre_facet |
Tromsø |
op_source |
ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation https://hal.science/hal-04000248 ISSAC 2023 - 48th International Symposium on Symbolic and Algebraic Computation, Jul 2023, Tromsø, Norway |
op_relation |
info:eu-repo/grantAgreement//101040794/EU/Transcendental methods in computational nonlinear algebra/10000 DIGITS hal-04000248 https://hal.science/hal-04000248 https://hal.science/hal-04000248v2/document https://hal.science/hal-04000248v2/file/arxiv_version.pdf |
op_rights |
info:eu-repo/semantics/OpenAccess |
_version_ |
1781707501537853440 |