The DMM bound: multivariate (aggregate) separation bounds
| Autor: | Bernard Mourrain, Elias P. Tsigaridas, Ioannis Z. Emiris |
|---|---|
| Přispěvatelé: | Department of Informatics and Telecomunications [Kapodistrian Univ] (DI NKUA), National and Kapodistrian University of Athens (NKUA), Geometry, algebra, algorithms (GALAAD), 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)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Aarhus], S. Watt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) |
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Symbolic Computation Polynomial Positive polynomial ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY 0102 computer and information sciences Symbolic Computation (cs.SC) 01 natural sciences Upper and lower bounds Matrix polynomial Square-free polynomial Combinatorics Integer matrix positive polynomial ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION separation bound Degree of a polynomial polynomial system 0101 mathematics Mathematics Discrete mathematics [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] Milne 010102 general mathematics Polynomial matrix 010201 computation theory & mathematics ACM: I.: Computing Methodologies/I.1: SYMBOLIC AND ALGEBRAIC MANIPULATION mixed volume |
| Zdroj: | Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, Jul 2010, Munich, Germany. pp.243-250, ⟨10.1145/1837934.1837981⟩ Emiris, I Z, Mourrain, B & Tsigaridas, E 2010, ' The DMM Bound : Multivariate (Aggregrate) Separation Bounds ', International Symposium on Symbolic and Algebraic Computation, pp. 243-250 . https://doi.org/10.1145/1837934.1837981 ISSAC |
| DOI: | 10.1145/1837934.1837981⟩ |
| Popis: | Best paper award; International audience; In this paper we derive aggregate separation bounds, named after Davenport-Mahler-Mignotte (\dmm), on the isolated roots of polynomial systems, specifically on the minimum distance between any two such roots. The bounds exploit the structure of the system and the height of the sparse (or toric) resultant by means of mixed volume, as well as recent advances on aggregate root bounds for univariate polynomials, and are applicable to arbitrary positive dimensional systems. We improve upon Canny's gap theorem \cite{c-crmp-87} by a factor of $\OO(d^{n-1})$, where $d$ bounds the degree of the polynomials, and $n$ is the number of variables. One application is to the bitsize of the eigenvalues and eigenvectors of an integer matrix, which also yields a new proof that the problem is polynomial. We also compare against recent lower bounds on the absolute value of the root coordinates by Brownawell and Yap \cite{by-issac-2009}, obtained under the hypothesis there is a 0-dimensional projection. Our bounds are in general comparable, but exploit sparseness; they are also tighter when bounding the value of a positive polynomial over the simplex. For this problem, we also improve upon the bounds in \cite{bsr-arxix-2009,jp-arxiv-2009}. Our analysis provides a precise asymptotic upper bound on the number of steps that subdivision-based algorithms perform in order to isolate all real roots of a polynomial system. This leads to the first complexity bound of Milne's algorithm \cite{Miln92} in 2D. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|