Solving Zero-Dimensional Systems through the Rational Univariate Representation

Fabrice Rouillier 1, 2
1 CALFOR - Calcul formel
LIP6 - Laboratoire d'Informatique de Paris 6
2 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : This paper is devoted to the resolution of zero-dimensional systems in $K[X_1,\ldots X_n]$, where $K$ is a field of characteristic zero (or strictly positive under some conditions). We follow the definition basically due to Kronecker for solving zero-dimensional systems : A system is solved if each root is represented in such way as to allow the performance of any arithmetical operations over the arithmetical expressions of its coordinates. We propose new definitions for solving zero-dimensional systems in this sense by introducing the Univariate Representation of their roots. We show by this way that the solutions of any zero-dimensional system of polynomials can be expressed through a special kind of univariate representation (Rational Univariate Representation): $$ \{ f(T)=0 \;,\; X_1=\frac{g_1(T)}{g(T)}\;,\; \ldots \;,\; X_n=\frac{g_n(T)}{g(T)} \} $$ where $(f,g,g_1,\ldots ,g_n)$ are polynomials of $K[X_1,\ldots ,X_n]$. A special feature of our Rational Univariate Representation is that we don't loose geometrical information contained in the initial system. Moreover we propose different efficient algorithms for the computation of the Rational Univariate Representation, and we make a comparison with standard known tools.
Type de document :
Article dans une revue
Applicable Algebra in Engineering, Communication and Computing, Springer Verlag, 1999, 9 (5), pp.433-461. 〈10.1007/s002000050114〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00098872
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:39:38
Dernière modification le : vendredi 31 août 2018 - 09:25:57

Lien texte intégral

Identifiants

Collections

Citation

Fabrice Rouillier. Solving Zero-Dimensional Systems through the Rational Univariate Representation. Applicable Algebra in Engineering, Communication and Computing, Springer Verlag, 1999, 9 (5), pp.433-461. 〈10.1007/s002000050114〉. 〈inria-00098872〉

Partager

Métriques

Consultations de la notice

256