logo EDITE Sujets de doctorat

Approximate Grobner Bases

Résumé rédigé par
Directeur de thèse:
Doctorant: Ye LIANG
Unité de recherche UMR 7606 Laboratoire d'informatique de Paris 6

Projet

The method of Grobner bases is an important tool for solving polynomial equations. Existing exact algorithms are usually CPU-intensive and memory-intensive when dealing with large systems consisting of polynomials with integer coefficients. Demands for higher efficiency and less cost of memory call for numerical computations using floating-point numbers. However, it has been reported in a vast literature that the numerical computation of Grobner bases is highly unstable.

In this thesis, the problem of instabilities is studied via a series of techniques on selecting suitable lengths of floating point numbers, tracing precision losses of coefficients of polynomials, recognizing zeros, and pivoting leading monomials of polynomials. Besides, we set up a theory for the phenomenon of artificial discontinuity in the single-parametric case.

We implemented our algorithms in Maple13 with these techniques to compute approximate Grobner bases. Experiments show that the algorithms can deal with nontrivial polynomial systems, though our implementations have large space to be optimized.