Files:

[PDF] 178.5kB  [gzipped postscript] 238.5kB  

Abstract:

We study polynomials of degree up to 4 over the rationals or a computable real subfield. Our motivation comes from the need to evaluate predicates in nonlinear computational geometry efficiently and exactly. We show a new method to compare real algebraic numbers by precomputing generalized Sturm sequences, thus avoiding iterative methods; the method, moreover handles all degenerate cases. Our first contribution is the determination of rational isolating points, as functions of the coefficients, between any pair of real roots. Our second contribution is to exploit invariants and Bezoutian subexpressions in writing the sequences, in order to reduce bit complexity. The degree of the tested quantities in the input coefficients is optimal for degree up to 3, and for degree 4 in certain cases. Our methods readily apply to real solving of pairs of quadratic equations, and to sign determination of polynomials over algebraic numbers of degree up to 4. Our third contribution is an implementation in a new module of library synaps v2.1. It improves significantly upon the efficiency of certain publicly available implementations: Rioboo's approach on axiom, the package of Guibas-Karavelas-Russel [11], and core v1.6, maple v9, and synaps v2.0. Some existing limited tests had shown that it is faster than commercial library leda v4.5 for quadratic algebraic numbers.

BibTeX:
@InProceedings{et-esa-04,
  Author =       {Ioannis~Z. Emiris and Elias~P. Tsigaridas},
  Title =        {Computing with real algebraic numbers of small
                  degree},
  BookTitle =    {Proc. 12th European Symp. of Algorithms (ESA)},
  Series =       "LNCS",
  Editor =       {S. Albers and T. Radzik},
  Volume =       3221,
  Pages =        "652--663",
  address =      {Bergen, Norway},
  month =        {Sep 14--17},
  Publisher =    "Springer Verlag",
  year =         2004,
  abstract =     "We study polynomials of degree up to 4 over the
                  rationals or a computable real subfield. Our
                  motivation comes from the need to evaluate
                  predicates in nonlinear computational geometry
                  efficiently and exactly. We show a new method to
                  compare real algebraic numbers by precomputing
                  generalized Sturm sequences, thus avoiding iterative
                  methods; the method, moreover handles all degenerate
                  cases. Our first contribution is the determination
                  of rational isolating points, as functions of the
                  coefficients, between any pair of real roots. Our
                  second contribution is to exploit invariants and
                  Bezoutian subexpressions in writing the sequences,
                  in order to reduce bit complexity. The degree of the
                  tested quantities in the input coefficients is
                  optimal for degree up to 3, and for degree 4 in
                  certain cases. Our methods readily apply to real
                  solving of pairs of quadratic equations, and to sign
                  determination of polynomials over algebraic numbers
                  of degree up to 4. Our third contribution is an
                  implementation in a new module of library synaps
                  v2.1. It improves significantly upon the efficiency
                  of certain publicly available implementations:
                  Rioboo's approach on axiom, the package of
                  Guibas-Karavelas-Russel [11], and core v1.6, maple
                  v9, and synaps v2.0. Some existing limited tests had
                  shown that it is faster than commercial library leda
                  v4.5 for quadratic algebraic numbers.",
}

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