publication . Conference object . Preprint . 2021

On FGLM Algorithms with Tate Algebras

Xavier Caruso; Tristan Vaccon; Thibaut Verron;
Open Access
  • Published: 18 Jul 2021
  • Publisher: ACM
  • Country: France
Abstract
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.
Persistent Identifiers

doi: 10.1145/3452143.3465521

Subjects
arXiv: Mathematics::Number Theory
ACM Computing Classification System: ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATIONGeneralLiterature_INTRODUCTORYANDSURVEY
free text keywords: p-adic precision, FGLM algorithm, Tate algebra, Gröbner bases, Algorithms, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Computer Science - Symbolic Computation, Context (language use), Formalism (philosophy), Signature (topology), Polynomial, Algorithm, Gröbner basis, Mathematics, Convergence (routing), Analytic geometry, Algebraic geometry
Related Organizations
View more
Funded by
ANR| CLap-CLap
Project
CLap-CLap
The p-adic Langlands correspondence: a constructive and algorithmic approach
  • Funder: French National Research Agency (ANR) (ANR)
  • Project Code: ANR-18-CE40-0026
, FWF| Integral D-finite Functions
Project
Integral D-finite Functions
  • Funder: Austrian Science Fund (FWF) (FWF)
  • Project Code: P 31571
  • Funding stream: Einzelprojekte
Download fromView all 7 versions
Open Access
arXiv.org e-Print Archive
Preprint . 2021
Providers: arXiv.org e-Print Archive
Open Access
Oskar Bordeaux
Conference object
Providers: Oskar Bordeaux
null
INRIA a CCSD electronic archive server; Hyper Article en Ligne; Mémoires en Sciences de l'Information et de la Communication; Hal-Diderot
Conference object . 2021
Providers: INRIA a CCSD electronic archive server; Hyper Article en Ligne; Mémoires en Sciences de l'Information et de la Communication; Hal-Diderot
null
https://doi.org/10.1145/345214...
Conference object . 2021
Providers: Crossref
18 references, page 1 of 2

[BvdHL11] Berthomieu, J., van der Hoeven, J., Lecerf, G., Relaxed algorithms for p-adic numbers, Journal de Théorie des Nombres de Bordeaux, 23(3):541-577, 2011.

[BL12] Berthomieu, J., Lebreton, R., Relaxed p-adic Hensel lifting for algebraic systems, In Proceedings of ISSAC'12, pages 59-66. ACM Press, 2012. [OpenAIRE]

[Bo14] Bosch, S., Lectures on Formal and Rigid Geometry, Lecture Notes in Mathematics 2105, Springer, 2014.

[CRV16] Caruso, X., Roe, D., Vaccon T., Division and Slope Factorization of p-Adic Polynomials , in Proceedings: ISSAC 2016, Waterloo, Canada.

[CRV17] Caruso, X., Roe, D., Vaccon T., Characteristic polynomials of p-adic matrices, in Proceedings: ISSAC 2017, Kaiserslautern, Germany.

[CVV19] Caruso, X., Vaccon T., Verron T., Gröbner bases over Tate algebras, in Proceedings: ISSAC 2019, Beijing, China.

[CVV20] Caruso, X., Vaccon T., Verron T., Signature-based algorithms for Gröbner bases over Tate algebras , in Proceedings: ISSAC 2020, Kalamata, Greece.

[FGLM93] Faugère, J.-C., Gianni, P., Lazard, D., Mora, T., E cient computation of zero-dimensional Gröbner bases by change of ordering, J. of Symbolic Computation 16 (4), 329-344, 1993 [OpenAIRE]

[FP04] Fresnel, J., van der Put, M., Rigid analytic geometry and its applications, Birkhäuser, 2004

[Go88] Gouvea, F., Arithmetic of ?-adic Modular Forms, Lecture Notes in Mathematics 1304, Springer-Verlag, 1988

[vdH97] van der Hoeven, J., Lazy multiplication of formal power series, in W. W. Küchlin, editor, Proc. ISSAC '97, pages 17-20, Maui, Hawaii, July 1997.

[IVY20] Ishihara, Y., Vaccon T., Yokoyama K., On FGLM Algorithms with Tropical Gröbner bases, in Proceedings: ISSAC 2020, Kalamata, Greece.

[KV04] Kaltofen, E., Villard, G., On the complexity of computing determinants, Comput. Complexity vol. 13, 2014

[KV20] Kulkarni, A., Vaccon, T., Super-linear convergence in the p-adic QRalgorithm, arxiv:2009.00129

[LS07] Le Stum Bernard, Rigid Cohomology, Cambridge tracts in mathematics 172, Cambridge University Press, 2007

18 references, page 1 of 2
graphPowered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue