Files:

[PDF] 273.4kB  [gzipped postscript] 242.7kB  

Abstract:

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. 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 strongly 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.

BibTeX:
@InProceedings{emt-issac-2010,
  author =       {Ioannis~Z. Emiris and Bernard Mourrain and
                  Elias~P. Tsigaridas},
  title =        {{The DMM bound: Multivariate (aggregate) separation
                  bounds}},
  booktitle =    ISSAC_2010,
  year =         2010,
  address =      {Munich, Germany},
  month =        {July},
  publisher =    {ACM},
  editor =       "S. Watt",
  pages =        "243--250",
  abstract =     "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.
                  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
                  strongly 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.",
}

Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02