Continued Fraction Expansion of Real Roots of Polynomial Systems

Angelos Mantzaflaris 1 Bernard Mourrain 1 Elias P. Tsigaridas 1
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 : We present a new algorithm for isolating the real roots of a system of multivariate polynomials, given in the monomial basis. It is inspired by existing subdivision methods in the Bernstein basis; it can be seen as generalization of the univariate continued fraction algorithm or alternatively as a fully analog of Bernstein subdivision in the monomial basis. The representation of the subdivided domains is done through homographies, which allows us to use only integer arithmetic and to treat efficiently unbounded regions. We use univariate bounding functions, projection and preconditionning techniques to reduce the domain of search. The resulting boxes have optimized rational coordinates, corresponding to the first terms of the continued fraction expansion of the real roots. An extension of Vincent's theorem to multivariate polynomials is proved and used for the termination of the algorithm. New complexity bounds are provided for a simplified version of the algorithm. Examples computed with a preliminary C++ implementation illustrate the approach.
Keywords : subdivision algorithm homography tensor monomial basis continued fractions C++ implementation
Type de document :
Communication dans un congrès
SNC, conference on Symbolic-Numeric Computation, Aug 2009, Kyoto, Japan. pp.85-94, 2009, 〈10.1145/1577190.1577207〉
Liste complète des métadonnées

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

mult2.jpg
mult2.jpg
https://hal.inria.fr/inria-00387399
Contributeur : Angelos Mantzaflaris <>
Soumis le : mercredi 10 novembre 2010 - 20:56:21
Dernière modification le : jeudi 11 janvier 2018 - 16:03:42
Document(s) archivé(s) le : vendredi 11 février 2011 - 02:33:55

Fichiers

snc-rr.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | UNICE | DIEUDONNE | UNIV-COTEDAZUR

Citation

Angelos Mantzaflaris, Bernard Mourrain, Elias P. Tsigaridas. Continued Fraction Expansion of Real Roots of Polynomial Systems. SNC, conference on Symbolic-Numeric Computation, Aug 2009, Kyoto, Japan. pp.85-94, 2009, 〈10.1145/1577190.1577207〉. 〈inria-00387399v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

345

Téléchargements de fichiers

226

Contact


archive-ouverte@inria.fr