On FGLM Algorithms with Tate Algebras
| Autor: | Xavier Caruso, Tristan Vaccon, Thibaut Verron |
|---|---|
| Přispěvatelé: | Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Lithe and fast algorithmic number theory (LFANT), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Johannes Kepler Universität Linz (JKU), This work was supported by the ANR project CLap–CLap (ANR-18-CE40-0026-01). T. Verron was supported by the Austrian FWF grant P31571-N32., Frédéric Chyzak, George Labahn and Marc Mezzarobba, ANR-18-CE40-0026,CLap-CLap,Correspondance de Langlands p-adique : une approche constructive et algorithmique(2018), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest |
| Rok vydání: | 2021 |
| Předmět: |
Computer Science - Symbolic Computation
FOS: Computer and information sciences Polynomial GeneralLiterature_INTRODUCTORYANDSURVEY Formalism (philosophy) Mathematics::Number Theory p-adic precision Context (language use) 0102 computer and information sciences Algebraic geometry Symbolic Computation (cs.SC) 01 natural sciences Gröbner basis Analytic geometry ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Convergence (routing) 0101 mathematics Tate algebra Mathematics [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] 010102 general mathematics FGLM algorithm 010201 computation theory & mathematics Gröbner bases Signature (topology) Algorithm Algorithms |
| Zdroj: | ISSAC International Symposium on Symbolic and Algebraic Computation — ISSAC 2021 International Symposium on Symbolic and Algebraic Computation — ISSAC 2021, Jul 2021, Virtual event, Russia |
| DOI: | 10.1145/3452143.3465521 |
| Popis: | International audience; Tate introduced in [Ta71] the notion of Tate algebras to serve, in the context of analytic geometry over the-adics, as a counterpart of polynomial algebras in classical algebraic geometry. In [CVV19, CVV20] the formalism of Gröbner bases over Tate algebras has been introduced and advanced signature-based algorithms have been proposed. In the present article, we extend the FGLM algorithm of [FGLM93] to Tate algebras. Beyond allowing for fast change of ordering, this strategy has two other important benefits. First, it provides an efficient algorithm for changing the radii of convergence which, in particular, makes effective the bridge between the polynomial setting and the Tate setting and may help in speeding up the computation of Gröbner basis over Tate algebras. Second, it gives the foundations for designing a fast algorithm for interreduction, which could serve as basic primitive in our previous algorithms and accelerate them significantly. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|