New bivariate system solver and topology of algebraic curves

Yacine Bouzidi 1 Sylvain Lazard 1 Marc Pouget 1 Fabrice Rouillier 2, 3
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We present a new approach for solving polynomial systems of two bivariate polynomials with rational coefficients. We first use González-Vega and Necula approach [3] based on sub-resultant sequences for decomposing a system into subsystems according to the number of roots (counted with multiplicities) in vertical lines. We then show how the resulting triangular subsystems can be efficiently solved by computing lexicographic Gröbner basis and Rational Univariate Representations (RURs) of these systems. We also show how this approach can be performed using modular arithmetic, while remaining deterministic. Finally we apply our solver to the problem of computing the topology of algebraic curves using the algorithm Isotop [2]. We show that our approach yields a substantial gain of a factor between 1 to 10 on curves of degree up to 28 compared to directly computing a Gröbner basis and RUR of the input system, and how it leads to a very competitive algorithm compared to the other state-of-the-art implementations.
Type de document :
Communication dans un congrès
27th European Workshop on Computational Geometry - EuroCG 2011, Mar 2011, Morschach, Switzerland. 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00580431
Contributeur : Marc Pouget <>
Soumis le : lundi 28 mars 2011 - 11:36:19
Dernière modification le : vendredi 25 mai 2018 - 12:02:04
Document(s) archivé(s) le : jeudi 8 novembre 2012 - 12:46:06

Fichier

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

Identifiants

  • HAL Id : inria-00580431, version 1

Collections

Citation

Yacine Bouzidi, Sylvain Lazard, Marc Pouget, Fabrice Rouillier. New bivariate system solver and topology of algebraic curves. 27th European Workshop on Computational Geometry - EuroCG 2011, Mar 2011, Morschach, Switzerland. 2011. 〈inria-00580431〉

Partager

Métriques

Consultations de la notice

587

Téléchargements de fichiers

134