Separation bounds for polynomial systems

Ioannis Emiris 1, 2 Bernard Mourrain 2 Elias Tsigaridas 3
2 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , National and Kapodistrian University of Athens
3 PolSys - Polynomial Systems
Inria de Paris, LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : We rely on aggregate separation bounds for univariate polynomials to introduce novel bounds for the isolated roots of zero-dimensional, as well as positive-dimensional and overdetermined, polynomial systems. We exploit the structure of the given system, as well as bounds on the height of the sparse (or toric) resultant, by means of mixed volume, thus establishing adaptive bounds. Our bounds improve Canny's gap theorem [9]. Moreover, they exploit sparseness. Our lower bounds are in general comparable to the lower bounds on the absolute value of the root coordinates by Brownawell and Yap [6] which, however, require the strong hypothesis of the existence of a zero-dimensional projection. In an effort to evaluate the quality of our bounds, we present polynomial systems whose root separation is asymptotically not far from our bounds. We apply our bounds to three important problems. First, we use them to estimate the bitsize of the eigenvalues and eigenvectors of an integer matrix; thus we provide yet another proof that the problem has polynomial bit complexity. Second, we bound the value of a positive polynomial over the simplex; we improve by at least one order of magnitude upon all existing bounds. Finally, we asymptotically bound the number of steps of any purely subdivision-based algorithm that isolates all real roots of a polynomial system.
Type de document :
Pré-publication, Document de travail
2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01105276
Contributeur : Elias Tsigaridas <>
Soumis le : mercredi 8 février 2017 - 13:36:40
Dernière modification le : jeudi 26 avril 2018 - 10:28:44
Document(s) archivé(s) le : mardi 9 mai 2017 - 12:12:25

Fichier

emt-dmm-j.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01105276, version 4

Collections

Citation

Ioannis Emiris, Bernard Mourrain, Elias Tsigaridas. Separation bounds for polynomial systems. 2017. 〈hal-01105276v4〉

Partager

Métriques

Consultations de la notice

364

Téléchargements de fichiers

176