Projet de recherche doctoral numero :3370


Date depot: 1 janvier 1900
Titre: Approximate Grobner Bases
Directeur de thèse: Jean-Charles FAUGÈRE (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini

Resumé: 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.

Doctorant.e: Liang Ye