Stable normal forms for polynomial system solving

Bernard Mourrain 1 Philippe Trébuchet 2
1 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
2 APR - Algorithmes, Programmes et Résolution
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : This paper describes and analyzes a method for computing border bases of a zero-dimensional ideal $I$. The criterion used in the computation involves specific commutation polynomials and leads to an algorithm and an implementation extending the one provided in [MT'05]. This general border basis algorithm weakens the monomial ordering requirement for \grob bases computations. It is up to date the most general setting for representing quotient algebras, embedding into a single formalism Gröbner bases, Macaulay bases and new representation that do not fit into the previous categories. With this formalism we show how the syzygies of the border basis are generated by commutation relations. We also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. This new feature for a symbolic algorithm has a huge impact on the practical efficiency as it is illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2008, 409 (2), pp.229-240. 〈10.1016/j.tcs.2008.09.004〉
Liste complète des métadonnées

Littérature citée [36 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00343103
Contributeur : Bernard Mourrain <>
Soumis le : samedi 29 novembre 2008 - 10:34:37
Dernière modification le : vendredi 12 janvier 2018 - 01:48:41
Document(s) archivé(s) le : lundi 7 juin 2010 - 23:34:44

Fichiers

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Bernard Mourrain, Philippe Trébuchet. Stable normal forms for polynomial system solving. Theoretical Computer Science, Elsevier, 2008, 409 (2), pp.229-240. 〈10.1016/j.tcs.2008.09.004〉. 〈inria-00343103〉

Partager

Métriques

Consultations de la notice

266

Téléchargements de fichiers

182