Files:
[PDF] 300.4kB [gzipped postscript] 233.3kB
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 subresultants-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.
BibTeX:
@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.",
}
Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02