Elias' Article

Univariate algebraic kernel and application to arrangement.
Sylvain Lazard, Luis Pe naranda, and Elias P. Tsigaridas.
In 8th Int. Symp. of Experimental Algorithms (SEA), pp. 209–220, LNCS 5526, Dortmund, Germany, 2009.

• Home
• Research
• Teaching
• Contact

Files:

[PDF] 379.5kB  [gzipped postscript] 130.8kB  

Abstract:

We present a \cgal-based univariate algebraic kernel, which provides certified real-root isolation of univariate polynomials with integer coefficients and standard functionalities such as basic arithmetic operations, greatest common divisor (gcd) and square-free factorization, as well as comparison and sign evaluations of real algebraic numbers. We compare our kernel with other comparable kernels, demonstrating the efficiency of our approach. Our experiments are performed on large data sets including polynomials of high degree (up to 2000) and with very large coefficients (up to 25000 bits per coefficient). We also address the problem of computing arrangements of $x$-monotone polynomial curves. We apply our kernel to this problem and demonstrate its efficiency compared to previous solutions available in \cgal.

@InProceedings{lpt-sea-2009,
  author =       {Sylvain Lazard and Luis Pe{\~n}aranda and
                  Elias~P. Tsigaridas},
  title =        {Univariate algebraic kernel and application to
                  arrangement},
  booktitle =    {8th Int. Symp. of Experimental Algorithms (SEA)},
  series =       "LNCS",
  volume =       5526,
  pages =        "209--220",
  year =         2009,
  address =      {Dortmund, Germany},
  editor =       {J. Vahrenhold},
  abstract =     " We present a \cgal-based univariate algebraic
                  kernel, which provides certified real-root isolation
                  of univariate polynomials with integer coefficients
                  and standard functionalities such as basic
                  arithmetic operations, greatest common divisor (gcd)
                  and square-free factorization, as well as comparison
                  and sign evaluations of real algebraic numbers.  We
                  compare our kernel with other comparable kernels,
                  demonstrating the efficiency of our approach.  Our
                  experiments are performed on large data sets
                  including polynomials of high degree (up to 2\,000)
                  and with very large coefficients (up to 25\,000 bits
                  per coefficient).  We also address the problem of
                  computing arrangements of $x$-monotone polynomial
                  curves. We apply our kernel to this problem and
                  demonstrate its efficiency compared to previous
                  solutions available in \cgal. ",
}

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