On Continued Fraction Expansion of Real Roots of Polynomial Systems, Complexity and Condition Numbers

Angelos Mantzaflaris 1 Bernard Mourrain 1 Elias Tsigaridas 1, 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 : We elaborate on a correspondence between the coeffcients of a multivariate polynomial represented in the Bernstein basis and in a tensor-monomial basis, which leads to homography representations of polynomial functions, that use only integer arithmetic (in contrast to Bernstein basis) and are feasible over unbounded regions. Then, we study an algorithm to split this representation and we obtain a subdivision scheme for the domain of multivariate polynomial functions. This implies a new algorithm for real root isolation, MCF, that generalizes the Continued Fraction (CF) algorithm of univariate polynomials. A partial extension of Vincent's Theorem for multivariate polynomials is presented, which allows us to prove the termination of the algorithm. Bounding functions, projection and preconditioning are employed to speed up the scheme. The resulting isolation boxes have optimized rational coordinates, corresponding to the first terms of the continued fraction expansion of the real roots. Finally, we present new complexity bounds for a simplified version of the algorithm in the bit complexity model, and also bounds in the real RAM model for a family of subdivision algorithms in terms of the real condition number of the system. Examples computed with our C++ implementation illustrate the practical aspects of our method.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2011, 412 (22), pp.2312-2330. 〈10.1016/j.tcs.2011.01.009〉
Liste complète des métadonnées

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


https://hal.inria.fr/inria-00530756
Contributeur : Angelos Mantzaflaris <>
Soumis le : vendredi 29 octobre 2010 - 18:14:48
Dernière modification le : jeudi 17 mai 2018 - 12:52:03
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 12:45:23

Fichiers

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

Identifiants

Collections

Citation

Angelos Mantzaflaris, Bernard Mourrain, Elias Tsigaridas. On Continued Fraction Expansion of Real Roots of Polynomial Systems, Complexity and Condition Numbers. Theoretical Computer Science, Elsevier, 2011, 412 (22), pp.2312-2330. 〈10.1016/j.tcs.2011.01.009〉. 〈inria-00530756〉

Partager

Métriques

Consultations de la notice

636

Téléchargements de fichiers

362