Hal will be stopped for maintenance from friday on june 10 at 4pm until monday june 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

Contributor : Elias Tsigaridas Connect in order to contact the contributor
Submitted on : Friday, December 25, 2015 - 10:04:52 PM
Last modification on : Friday, January 21, 2022 - 3:15:31 AM


Files produced by the author(s)



Aaron Herman, Elias Tsigaridas. Bounds for the Condition Number of Polynomials Systems with Integer Coefficients. CASC, 2015, Aachen, Germany. pp.210--219, ⟨10.1007/978-3-319-24021-3_16⟩. ⟨hal-01248389⟩



Record views


Files downloads