### 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.

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

# Related Articles

**2019-03-08**

1903.03278 | cs.SC

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

**2019-05-12**

1905.04614 | cs.SC

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

**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

**2017-02-23**

1702.07262 | math.AC

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

**2018-09-28**

1809.10971 | math.AG

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

**2018-03-21**

1803.07974 | math.AG

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

**2019-02-01**

1902.00208 | cs.SC

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

**2017-12-12**

1712.04177 | cs.SC

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

**2014-04-17**

1404.5525 | cs.NA

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

**2012-06-19**

1206.4224 | cs.CC

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

**2016-01-06**

1601.01067 | cs.SC

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

**2013-11-22**

1311.5694 | cs.SC

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

**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

**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

**2013-11-15**

1311.3731 | cs.DS

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

**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