Solving polynomial systems. Algorithms and Applications.

Jean-Charles Faugère 1
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : This talk presents new algorithms for solving polynomial systems and in particular two new efficient algorithms for computing Gröbner bases. To avoid as much as possible intermediate computation, the F4 algorithm computes successive truncated Gröbner bases and replaces the classical polynomial reduction found in the Buchberger algorithm by the simultaneous reduction of several polynomials. This powerful reduction mechanism is achieved by means of a symbolic precomputation and by extensive use of sparse linear algebra methods. A second algorithm, called F5, eliminate the Buchberger criteria so that there is no reduction to zero during the computation when the input system is a regular sequence. In a second part of the talk we review different applications solved by these algorithms/programs (Robotic, Cryptography, N body problem, Coding theory, ...).
Keywords : applications groebner
Type de document :
Communication dans un congrès
Computer Algebra in Applications to Integrable Systems, 2001, Cambridge, England, 2001
Liste complète des métadonnées
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:48:55
Dernière modification le : mercredi 9 mai 2018 - 15:46:12


  • HAL Id : inria-00100675, version 1



Jean-Charles Faugère. Solving polynomial systems. Algorithms and Applications.. Computer Algebra in Applications to Integrable Systems, 2001, Cambridge, England, 2001. 〈inria-00100675〉



Consultations de la notice