Elias' Article

Continued fraction expansion of real roots of polynomial systems.
Angelos Mantzaflaris, Bernard Mourrain, and Elias P. Tsigaridas.
In Proc. 3rd ACM Int'l Work. Symbolic Numeric Computation (SNC), pp. 85–94, ACM, Kyoto, Japan, 2009.

• Home
• Research
• Teaching
• Contact

Files:

[PDF] 546.2kB  [gzipped postscript] 801.0kB  

Abstract:

We present a new algorithm for isolating the real roots of a system of multivariate polynomials, given in the monomial basis. It is inspired by existing subdivision methods in the Bernstein basis; it can be seen as generalization of the univariate continued fraction algorithm or alternatively as a fully analog of Bernstein subdivision in the monomial basis. The representation of the subdivided domains is done through homographies, which allows us to use only integer arithmetic and to treat efficiently unbounded regions. We use univariate bounding functions, projection and preconditioning techniques to reduce the domain of search. The resulting boxes have optimized rational coordinates, corresponding to the first terms of the continued fraction expansion of the real roots. An extension of Vincent's Theorem to multivariate polynomials is established and used to prove termination of the algorithm. New complexity bounds are provided for a simplified version of the algorithm. Examples computed with our C++ implementation illustrate the approach.

@InProceedings{mmt-mcf-snc-2009,
  author =       {Angelos Mantzaflaris and Bernard Mourrain and Elias
                  P. Tsigaridas},
  title =        {Continued fraction expansion of real roots of
                  polynomial systems},
  booktitle =    SNC_2009,
  year =         2009,
  isbn =         {978-1-60558-664-9},
  pages =        {85--94},
  address =      {Kyoto, Japan},
  publisher =    {ACM},
  editor =       {H. Kai and H. Sekigawa},
  abstract =     " We present a new algorithm for isolating the real
                  roots of a system of multivariate polynomials, given
                  in the \emph{monomial basis}. It is inspired by
                  existing subdivision methods in the Bernstein basis;
                  it can be seen as generalization of the univariate
                  continued fraction algorithm or alternatively as a
                  fully analog of Bernstein subdivision in the
                  monomial basis.  The representation of the
                  subdivided domains is done through
                  \emph{homographies}, which allows us to use only
                  integer arithmetic and to treat efficiently
                  unbounded regions.  We use univariate bounding
                  functions, projection and preconditioning techniques
                  to reduce the domain of search. The resulting boxes
                  have optimized rational coordinates, corresponding
                  to the first terms of the \emph{continued fraction
                  expansion} of the real roots.  An extension of
                  \emph{Vincent's Theorem} to multivariate polynomials
                  is established and used to prove termination of the
                  algorithm. New complexity bounds are provided for a
                  simplified version of the algorithm.  Examples
                  computed with our C++ implementation illustrate the
                  approach.",
}

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