Matrix-F5 algorithms over finite-precision complete discrete valuation fields

DOI10.1145/2608628.2608658zbMATH Open1362.13030arXiv1403.5464OpenAlexW2407324517MaRDI QIDQ5891054FDOQ5891054

Authors: Tristan Vaccon 

Publication date: 29 November 2016

Published in: Journal of Symbolic Computation, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Abstract: Let $(f_1,dots,f_s)inmathbb{Q}_p[X_1,dots,X_n{]}^s$ be a sequence of homogeneous polynomials with $p$-adic coefficients. Such system may happen, for example, in arithmetic geometry. Yet, since $mathbb{Q}_p$ is not an effective field, classical algorithm does not apply.We provide a definition for an approximate Gr{"o}bner basis with respect to a monomial order $w.$ We design a strategy to compute such a basis, when precision is enough and under the assumption that the input sequence is regular and the ideals $langle{f}_1,dots,f_{i}angle$ are weakly-$w$-ideals. The conjecture of Moreno-Socias states that for the grevlex ordering, such sequences are generic.Two variants of that strategy are available, depending on whether one lean more on precision or time-complexity. For the analysis of these algorithms, we study the loss of precision of the Gauss row-echelon algorithm, and apply it to an adapted Matrix-F5 algorithm. Numerical examples are provided.Moreover, the fact that under such hypotheses, Gr{"o}bner bases can be computed stably has many applications. Firstly, the mapping sending $(f_1,dots,f_s)$ to the reduced Gr{"o}bner basis of the ideal they span is differentiable, and its differential can be given explicitly. Secondly, these hypotheses allows to perform lifting on the Grobner bases, from $mathbbZ/p^{k}mathbbZ$ to $mathbbZ/p^{k+k^{\prime }}mathbbZ$ or $mathbbZ.$ Finally, asking for the same hypotheses on the highest-degree homogeneous components of the entry polynomials allows to extend our strategy to the affine case.

Full work available at URL: https://arxiv.org/abs/1403.5464

Recommendations

• Matrix-F5 algorithms over finite-precision complete discrete valuation fields
• Refined F5 Algorithms for Ideals of Minors of Square Matrices
• Computing in unitriangular matrices over finite fields
• scientific article; zbMATH DE number 7161398
• Fast randomized algorithms for the structure of matrix algebras over finite fields (extended abstract)
• Efficient multiplication in finite field extensions of degree 5
• On the complexity of the \(F_5\) Gröbner basis algorithm
• Algorithms for finite field arithmetic

zbMATH Keywords

regular sequenceF5 algorithm\(p\)-adic algorithm\(p\)-adic precisionGröbner basesapproximate Gröbner basislifing of Gröbner basesmatrix-F5 algorithmMoreno-Socias conjectureweakly-\(w\)-ideal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Valuation rings (13F30) Polynomials, factorization in commutative rings (13P05)

Cites Work

• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Ring-theoretic properties of certain Hecke algebras
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Modular algorithms for computing Gröbner bases.
• Title not available (Why is that?)
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Title not available (Why is that?)
• Deformations of Galois Representations
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Introduction to the solution of polynomial systems
• An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
• Title not available (Why is that?)
• Generic initial ideals of points and curves
• Tracking \(p\)-adic precision
• Title not available (Why is that?)
• On lucky ideals for Gröbner basis computations
• Modularity for some geometric Galois representations. With an appendix by Ofer Gabber.
• Term cancellations in computing floating-point Gröbner bases
• Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity
• Artificial discontinuities of single-parametric Gröbner bases
• Definability and decision problems in arithmetic
• Cylindrical algebraic decomposition using validated numerics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Jordan Curve Theorem, Formally and Informally
• Generic sequences of polynomials
• On the complexity of computing Gröbner bases for quasi-homogeneous systems
• A p-adic approach to the computation of Gröbner bases
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithmic Number Theory
• On lucky primes
• Remarks on automatic algorithm stabilization
• Gröbner bases over fields with valuations
• Sub-cubic change of ordering for Gröbner basis: a probabilistic approach
• Deformations and the rigidity method
• A Study on Gröbner Basis with Inexact Input
• Matrix-F5 algorithms over finite-precision complete discrete valuation fields
• Computing floating-point Gröbner bases accurately
• \(P\)-adic stability in linear algebra
• [[Publication:2878808|Linear algebra over \(\mathbb Z_pu\) and related rings]]

Cited In (7)

• Computing tropical varieties over fields with valuation using classical standard basis techniques
• Matrix-F5 algorithms over finite-precision complete discrete valuation fields
• Computing tropical varieties over fields with valuation
• On affine tropical F5 algorithms
• Refined F5 Algorithms for Ideals of Minors of Square Matrices
• Matrix-F5 algorithms and tropical Gröbner bases computation
• A p-adic approach to the computation of Gröbner bases

Uses Software

• SageMath
• Jordan

This page was built for publication: Matrix-F5 algorithms over finite-precision complete discrete valuation fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891054)