Separation bounds for polynomial systems
| Autor: | Elias P. Tsigaridas, Ioannis Z. Emiris, Bernard Mourrain |
|---|---|
| Přispěvatelé: | AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), National and Kapodistrian University of Athens (NKUA), OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Ioannis Emiris and Bernard Mourrain acknowledge partial support by the EU H2020 research and innovation program, under the Marie Sklodowska-Curie grant agreement No 675789: Network 'ARCADES'. Elias Tsigaridas is partially supported by ANR JCJC GALOP (ANR-17-CE40-0009), the PGMO grant ALMA and the PHC Bosphore programGRAPE, ANR-17-CE40-0009,GALOP,Jeux à travers la lentille de algèbre et géométrie de l'optimisation(2017) |
| Rok vydání: | 2020 |
| Předmět: |
Polynomial
Separation bounds Positive polynomial 010103 numerical & computational mathematics Separation bound 01 natural sciences Projection (linear algebra) Square-free polynomial Matrix polynomial Sparse resultant Combinatorics Overdetermined system Integer matrix ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Degree of a polynomial 0101 mathematics DMM Mathematics [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] Discrete mathematics Algebra and Number Theory Height of the resultant [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic 010102 general mathematics Subdivision algorithm Computational Mathematics Arithmetic Nullstellensätze Polynomial system |
| Zdroj: | Journal of Symbolic Computation Journal of Symbolic Computation, 2020, 101, pp.128-151. ⟨10.1016/j.jsc.2019.07.001⟩ Journal of Symbolic Computation, Elsevier, 2020, 101, pp.128-151. ⟨10.1016/j.jsc.2019.07.001⟩ |
| ISSN: | 0747-7171 1095-855X |
| DOI: | 10.1016/j.jsc.2019.07.001 |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect