@COMMENT {Autogenerated file by bib2html.pl version 0.94}
@InProceedings{det-issac-2007,
author = {Dimitris~I. Diochnos and Ioannis~Z. Emiris and
Elias~P. Tsigaridas},
title = {On the complexity of real solving bivariate systems},
booktitle = ISSAC_2007,
pages = "127--134",
year = 2007,
editor = {C.~W. Brown},
address = {Waterloo, Canada},
abstract = " We consider exact real solving of well-constrained,
bivariate systems of relatively prime polynomials.
The main problem is to compute all common real roots
in isolating interval representation, and to
determine their intersection multiplicities. We
present three algorithms and analyze their
asymptotic bit complexity, obtaining a bound of
$\sOB(N^(14))$ for the purely projection-based
method, and $\sOB(N^(12))$ for two
sub\-result\-ants-based methods: these ignore
polylogarithmic factors, and $N$ bounds the degree
and the bitsize of the polynomials. The previous
record bound was $\sOB(N^(14))$. Our main tool is
signed subresultant sequences, extended to several
variables by binary segmentation. We exploit
advances on the complexity of univariate root
isolation, and extend them to multipoint sign
evaluation, sign evaluation of bivariate polynomials
over two algebraic numbers, % We thus derive new
bounds for the sign evaluation of bi- and
multi-variate polynomials and real root counting
over an extension field. Our algorithms apply to
the problem of simultaneous inequalities; they also
compute the topology of real plane algebraic curves
in $\sOB( N^(12))$, whereas the previous bound was
$\sOB( N^(14))$. All algorithms have been
implemented in \maple, in conjunction with numeric
filtering. We compare them against \gbrs and
\synaps; we also consider \maple libraries INSULATE
and TOP, which compute curve topology. Our software
is among the most robust, and its runtimes are
within a small constant factor, with respect to the
\cc/\cpp libraries.",
}