Bounds for the Condition Number of Polynomials Systems with Integer Coefficients

Aaron Herman 1 Elias Tsigaridas 2
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Polynomial systems of equations are a central object of study in computer algebra. Among the many existing algorithms for solving polynomial systems, perhaps the most successful numerical ones are the homotopy algorithms. The number of operations that these algorithms perform depends on the condition number of the roots of the polynomial system. Roughly speaking the condition number expresses the sensitivity of the roots with respect to small perturbation of the input coefficients. A natural question to ask is how can we bound, in the worst case, the condition number when the input polynomials have integer coefficients? We address this problem and we provide effective bounds that depend on the number of variables, the degree and the maximum coefficient bitsize of the input polynomials. Such bounds allows to estimate the bit complexity of the algorithms that depend on the separation bound, like the homotopy algorithms, for solving polynomial systems.
Type de document :
Communication dans un congrès
Vladimir P. Gerdt and Wolfram Koepf and Werner M. Seiler and Evgenii V. Vorozhtsov. CASC, 2015, Aachen, Germany. 9301, pp.210--219, 2015, 〈10.1007/978-3-319-24021-3_16〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01248389
Contributeur : Elias Tsigaridas <>
Soumis le : vendredi 25 décembre 2015 - 22:04:52
Dernière modification le : jeudi 11 janvier 2018 - 06:24:00

Fichier

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

Identifiants

Collections

Citation

Aaron Herman, Elias Tsigaridas. Bounds for the Condition Number of Polynomials Systems with Integer Coefficients. Vladimir P. Gerdt and Wolfram Koepf and Werner M. Seiler and Evgenii V. Vorozhtsov. CASC, 2015, Aachen, Germany. 9301, pp.210--219, 2015, 〈10.1007/978-3-319-24021-3_16〉. 〈hal-01248389〉

Partager

Métriques

Consultations de la notice

204

Téléchargements de fichiers

74