On the Complexity of Solving a Bivariate Polynomial System

Details On the Complexity of Solving a Bivariate Polynomial System On the Complexity of Solving a Bivariate Polynomial System

2011-04-26

arxiv.org/abs/1104.4954v1

Computer Science

Symbolic Computation

Scientific paper

We study the complexity of computing the real solutions of a bivariate polynomial system using the recently proposed algorithm BISOLVE. BISOLVE is a classical elimination method which first projects the solutions of a system onto the $x$- and $y$-axes and, then, selects the actual solutions from the so induced candidate set. However, unlike similar algorithms, BISOLVE requires no genericity assumption on the input nor it needs any change of the coordinate system. Furthermore, extensive benchmarks from \cite{bes-bisolve-2011} confirm that the algorithm outperforms state of the art approaches by a large factor. In this work, we show that, for two polynomials $f,g\in\mathbb{Z}[x,y]$ of total degree at most $n$ with integer coefficients bounded by $2^\tau$, BISOLVE computes isolating boxes for all real solutions of the system $f=g=0$ using $\Otilde(n^8\tau^{2})$ bit operations, thereby improving the previous record bound by a factor of at least $n^{2}$.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Solving a Bivariate Polynomial System does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Complexity of Solving a Bivariate Polynomial System, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Solving a Bivariate Polynomial System will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-296672