ML p(r)ior | On the p-adic stability of the FGLM algorithm

On the p-adic stability of the FGLM algorithm

2016-02-02
1602.00848 | cs.SC
Nowadays, many strategies to solve polynomial systems use the computation of a Gr{\"o}bner basis for the graded reverse lexicographical ordering, followed by a change of ordering algorithm to obtain a Gr{\"o}bner basis for the lexicographical ordering. The change of ordering algorithm is crucial for these strategies. We study the p-adic stability of the main change of ordering algorithm, FGLM. We show that FGLM is stable and give explicit upper bound on the loss of precision occuring in its execution. The variant of FGLM designed to pass from the grevlex ordering to a Gr{\"o}bner basis in shape position is also stable. Our study relies on the application of Smith Normal Form computations for linear algebra.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2019-03-08

It is well known that for any finite Galois extension field $K/F$, with Galois group $G = \mathrm{Ga… show more
PDF

Highlights - Most important sentences from the article

2019-05-12

Following recent work by van der Hoeven and Lecerf (ISSAC 2017), we discuss the complexity of linear… show more
PDF

Highlights - Most important sentences from the article

2019-04-05
1904.04072 | math.AG

Given an ideal $I$ and a polynomial $f$ the {Ideal Membership Problem} is to test if $f\in I$. This … show more
PDF

Highlights - Most important sentences from the article

2017-02-23

Given a zero-dimensional ideal I in a polynomial ring, many computations start by finding univariate… show more
PDF

Highlights - Most important sentences from the article

2018-09-28

We investigate the application of syzygies for efficiently computing (finite) Pommaret bases. For th… show more
PDF

Highlights - Most important sentences from the article

2018-03-21

We consider the problem of finding the isolated common roots of a set of polynomial functions defini… show more
PDF

Highlights - Most important sentences from the article

2019-02-01

Gr{\"o}bner bases is one the most powerful tools in algorithmic non-linear algebra. Their computatio… show more
PDF

Highlights - Most important sentences from the article

2017-12-12

Consider a zero-dimensional ideal $I$ in $\mathbb{K}[X_1,\dots,X_n]$. Inspired by Faug\`ere and Mou'… show more
PDF

Highlights - Most important sentences from the article

2014-04-17

In this paper, we study iterative methods on the coefficients of the rational univariate representat… show more
PDF

Highlights - Most important sentences from the article

2012-06-19

We present an algorithm which computes the multilinear factors of bivariate lacunary polynomials. It… show more
PDF

Highlights - Most important sentences from the article

2016-01-06

In this paper, a polynomial-time algorithm is given to compute the generalized Hermite normal form f… show more
PDF

Highlights - Most important sentences from the article

2013-11-22

We present a deterministic polynomial-time algorithm which computes the multilinear factors of multi… show more
PDF

Highlights - Most important sentences from the article

2014-08-09
1408.2095 | cs.CG

We present a Kedlaya-style point counting algorithm for cyclic covers $y^r = f(x)$ over a finite fie… show more
PDF

Highlights - Most important sentences from the article

2018-02-23
1802.08532 | math.NT

We present a new package ZpL for the mathematical software system SM. It implements a sharp tracking… show more
PDF

Highlights - Most important sentences from the article

2013-11-15

Our Chapter in the upcoming Volume I: Computer Science and Software Engineering of Computing Handboo… show more
PDF

Highlights - Most important sentences from the article

2018-02-07
1802.02270 | cs.SC

We present new algorithms to detect and correct errors in the product of two matrices, or the invers… show more
PDF

Highlights - Most important sentences from the article