Elias' Article

Real solving of bivariate polynomial systems.
Ioannis Z. Emiris and Elias P. Tsigaridas.
In Proc. Computer Algebra in Scientific Computing (CASC), pp. 150–161, LNCS 3718, Springer, 2005.

• Home
• Research
• Teaching
• Contact

Files:

[PDF] 168.6kB  [gzipped postscript] 225.3kB  

Abstract:

We propose exact, complete and efficient methods for 2 problems: First, the real solving of systems of two bivariate rational polynomials of arbitrary degree. This means isolating all common real solutions in rational rectangles and calculating the respective multiplicities. Second, the computation of the sign of bivariate polynomials evaluated at two algebraic numbers of arbitrary degree. Our main motivation comes from nonlinear computational geometry and computer-aided design, where bivariate polynomials lie at the inner loop of many algorithms. The methods employed are based on Sturm-Habicht sequences, univariate resultants and rational univariate representation. We have implemented them very carefully, using advanced object-oriented programming techniques, so as to achieve high practical performance. The algorithms are integrated in the public-domain C++ software library synaps, and their efficiency is illustrated by 9 experiments against existing implementations. Our code is faster in most cases; sometimes it is even faster than numerical approaches.

@InProceedings{et-casc-2005,
  author =       {Ioannis~Z. Emiris and Elias~P. Tsigaridas},
  title =        {Real solving of bivariate polynomial systems},
  booktitle =    {Proc. Computer Algebra in Scientific Computing
                  (CASC)},
  pages =        {150--161},
  year =         2005,
  editor =       {V. Ganzha and E. Mayr},
  volume =       3718,
  series =       {LNCS},
  publisher =    {Springer},
  abstract =     "We propose exact, complete and efficient methods for
                  2 problems: First, the real solving of systems of
                  two bivariate rational polynomials of arbitrary
                  degree. This means isolating all common real
                  solutions in rational rectangles and calculating the
                  respective multiplicities. Second, the computation
                  of the sign of bivariate polynomials evaluated at
                  two algebraic numbers of arbitrary degree. Our main
                  motivation comes from nonlinear computational
                  geometry and computer-aided design, where bivariate
                  polynomials lie at the inner loop of many
                  algorithms. The methods employed are based on
                  Sturm-Habicht sequences, univariate resultants and
                  rational univariate representation. We have
                  implemented them very carefully, using advanced
                  object-oriented programming techniques, so as to
                  achieve high practical performance. The algorithms
                  are integrated in the public-domain C++ software
                  library synaps, and their efficiency is illustrated
                  by 9 experiments against existing implementations.
                  Our code is faster in most cases; sometimes it is
                  even faster than numerical approaches.",
}

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