Separation bounds for polynomial systems

Ioannis Emiris 1, 2 Bernard Mourrain 1 Elias Tsigaridas 3
1 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
Abstract : We rely on aggregate separation bounds for univariate polynomials to introduce novel worst-case separation bounds for the isolated roots of zero-dimensional, positive-dimensional, and overde- termined 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 upon Canny’s Gap theorem [9]. Moreover, they exploit sparseness and they apply without any assumptions on the input polynomial system. To evaluate the quality of the bounds, we present polynomial systems whose root separation is asymptotically not far from our bounds. We apply our bounds to three problems. First, we use them to estimate the bitsize of the eigenvalues and eigenvectors of an integer matrix; thus we provide a new 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.
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download

https://hal.inria.fr/hal-01105276
Contributor : Elias Tsigaridas <>
Submitted on : Friday, June 28, 2019 - 7:23:54 PM
Last modification on : Wednesday, October 23, 2019 - 5:24:16 PM

File

emt-dmm-j.pdf
Files produced by the author(s)

Identifiers

Citation

Ioannis Emiris, Bernard Mourrain, Elias Tsigaridas. Separation bounds for polynomial systems. Journal of Symbolic Computation, Elsevier, 2019, ⟨10.1016/j.jsc.2019.07.001⟩. ⟨hal-01105276v5⟩

Share

Metrics

Record views

76

Files downloads

389