Elias' Article

Real algebraic numbers and polynomial systems of small degree.
Ioannis Z. Emiris and Elias P. Tsigaridas.
Theor. Comput. Sci., 409(2):186 – 199, 2008. (Special issue on Symbolic-Numeric Computations)

HAL version available here.

• Home
• Research
• Teaching
• Contact

Files:

[PDF] 328.9kB  [gzipped postscript] 690.6kB  

Abstract:

Based on precomputed Sturm-Habicht sequences, discriminants and invariants, we classify, isolate with rational points, and compare the real roots of polynomials of degree up to 4. In particular, we express all isolating points as rational functions of the input polynomial coefficients. Although the roots are algebraic numbers and can be expressed by radicals, such representation involves some roots of complex numbers. This is inefficient and hard to handle in applications to geometric computing and quantifier elimination. We also define rational isolating points between the roots of the quintic. % We combine these results with a simple version of Rational Univariate Representation to isolate all common real roots of a bivariate system of rational polynomials of total degree $łeq 2$ and to compute the multiplicity of these roots. % We present our software within \synaps and perform experiments and comparisons with several public-domain implementations. Our package is 2--10 times faster than numerical methods and exact subdivision-based methods, including software with intrinsic filtering.

@Article{et-tcs-snc-2008,
  author =       "Ioannis Z. Emiris and Elias P. Tsigaridas",
  title =        "Real algebraic numbers and polynomial systems of
                  small degree",
  journal =      TCS,
  volume =       409,
  number =       2,
  pages =        "186 - 199",
  year =         2008,
  note =         "(Special issue on Symbolic-Numeric Computations)",
  issn =         "0304-3975",
  url =
                  "http://www.science-direct.com/science/article/B6V1G-4TFW9FJ-1/2/8f6bb0cb34b1de545d66993001ac64c0",
  keywords =     "Algebraic number",
  keywords =     "Bivariate polynomial",
  keywords =     "Quartic",
  keywords =     "Sturm sequence",
  abstract =     " Based on precomputed Sturm-Habicht sequences,
                  discriminants and invariants, we classify, isolate
                  with rational points, and compare the real roots of
                  polynomials of degree up to~4. In particular, we
                  express all isolating points as rational functions
                  of the input polynomial coefficients.  Although the
                  roots are algebraic numbers and can be expressed by
                  radicals, such representation involves some roots of
                  complex numbers.  This is inefficient and hard to
                  handle in applications to geometric computing and
                  quantifier elimination.  We also define rational
                  isolating points between the roots of the quintic.
                  % We combine these results with a simple version of
                  Rational Univariate Representation to isolate all
                  common real roots of a bivariate system of rational
                  polynomials of total degree $\leq 2$ and to compute
                  the multiplicity of these roots.  % We present our
                  software within \synaps and perform experiments and
                  comparisons with several public-domain
                  implementations.  Our package is 2--10 times faster
                  than numerical methods and exact subdivision-based
                  methods, including software with intrinsic
                  filtering.",
}

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