Generalized normal forms and polynomial system solving

Bernard Mourrain 1 Philippe Trebuchet 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
Abstract : This report describes a new method for computing the normal form of a polynomial modulo a zero-dimensional ideal $I$. We give a detailed description of the algorithm, a proof of its correctness, and finally experimentations on classical benchmark polynomial systems. The method that we propose can be thought as an extension of both the Gröbner basis method and the Macaulay construction. As such it establishes a natural link between these two methods. We have weaken the monomial ordering requirement for Gröbner bases computations, which allows us to construct new type of representations for the associated quotient algebra. This approach yields more freedom in the linear algebra steps involved, which allows us to take into account numerical criteria while performing the symbolic steps. This is a new feature for a symbolic algorithm, which has an important impact on the practical efficiency, as it is illustrated by the experiments at the end of the paper.
Document type :
Conference papers
Liste complète des métadonnées

https://hal.inria.fr/inria-00070537
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:48:28 PM
Last modification on : Wednesday, April 17, 2019 - 4:08:00 PM
Document(s) archivé(s) le : Sunday, April 4, 2010 - 9:25:45 PM

Identifiers

Citation

Bernard Mourrain, Philippe Trebuchet. Generalized normal forms and polynomial system solving. ISSAC 2005 - International Symposium on Symbolic and Algebraic Computation , Jul 2005, Beijing, China. pp.253-260, ⟨10.1145/1073884.1073920⟩. ⟨inria-00070537⟩

Share

Metrics

Record views

277

Files downloads

284