The DMM bound: multivariate (aggregate) separation bounds - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2009

The DMM bound: multivariate (aggregate) separation bounds

Résumé

In this paper we present aggregate separation bounds for polynomials systems. We call the bounds Davenport-Mahler-Mignotte (\dmm), and we prove that in most of the cases are close to optimal. The bounds are output-sensitive in the sense that they depend on the mixed volume of the tested systems. As a consequence, we improve the gap theorem \cite{c-crmp-87} of Canny by a factor of $d^{n-1}$, where $d$ is a bound on the degree of the polynomials, and $n$ is their number. We apply our bounds on the problem of computing the eigenvalues and eigenvectors of an integer matrix, and we improve the bound of \cite{bsr-arxix-2009} on the minimum of value of a positive polynomial over the standard simplex. We also apply our bounds to find a lower bound on the number of steps that a subdivision-based algorithm for polynomial system solving should perform, we provide for the first time the complexity of Milne's algorithm in the 2D
Fichier principal
Vignette du fichier
DMM.pdf (331.91 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00393833 , version 1 (09-06-2009)
inria-00393833 , version 2 (09-06-2009)
inria-00393833 , version 3 (12-05-2010)
inria-00393833 , version 4 (10-06-2010)

Identifiants

  • HAL Id : inria-00393833 , version 1

Citer

Ioannis Z. Emiris, Bernard Mourrain, Elias P. P. Tsigaridas. The DMM bound: multivariate (aggregate) separation bounds. [Research Report] 2009. ⟨inria-00393833v1⟩
335 Consultations
332 Téléchargements

Partager

Gmail Facebook X LinkedIn More