Continued Fraction Expansion of Real Roots of Polynomial Systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Continued Fraction Expansion of Real Roots of Polynomial Systems

Angelos Mantzaflaris
Bernard Mourrain
Elias P. P. Tsigaridas

Résumé

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.
Fichier principal
Vignette du fichier
snc-rr.pdf (450.89 Ko) Télécharger le fichier
Vignette du fichier
mult2.jpg (31.65 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Loading...

Dates et versions

inria-00387399 , version 1 (25-05-2009)
inria-00387399 , version 2 (10-11-2010)

Identifiants

Citer

Angelos Mantzaflaris, Bernard Mourrain, Elias P. P. Tsigaridas. Continued Fraction Expansion of Real Roots of Polynomial Systems. SNC, conference on Symbolic-Numeric Computation, Aug 2009, Kyoto, Japan. pp.85-94, ⟨10.1145/1577190.1577207⟩. ⟨inria-00387399v2⟩
182 Consultations
669 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More