Matrix-F5 algorithms over finite-precision complete discrete valuation fields
详细信息 查看全文
- 作者：Tristan Vaccona ; b ; vaccon@rikkyo.ac.jp ;
- 关键词：F5 algorithm ; Grö ; bner bases ; Moreno-Socias conjecture ; p-Adic algorithm ; p-Adic precision ; Differential precision
- 刊名：Journal of Symbolic Computation
- 出版年：2017
- 出版时间：May-June 2017
- 年：2017
- 卷：80
- 期：part_P2
- 页码：329-350
- 全文大小：574 K
- 卷排序：80
文摘
Let (f1,…,fs)∈Qp[X1,…,Xn]s(f1,…,fs)∈Qp[X1,…,Xn]s be a sequence of homogeneous polynomials with p -adic coefficients. Such system may happen, for example, in arithmetic geometry. Yet, since QpQp is not an effective field, classical algorithm does not apply.We provide a definition for an approximate Grö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 〈f1,…,fi〉〈f1,…,fi〉 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 leans 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öbner bases can be computed stably has many applications. Firstly, the mapping sending (f1,…,fs)(f1,…,fs) to the reduced Gröbner basis of the ideal they span is differentiable, and its differential can be given explicitly. Secondly, these hypotheses allow to perform lifting on the Grobner bases, from Z/pkZZ/pkZ to Z/pk+k′ZZ/pk+k′Z or ZZ.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.