Files:
[PDF] 327.5kB [gzipped postscript] 273.5kB
Abstract:
This paper is concerned with exact real solving of well-constrained, bivariate polynomial systems. The main problem is to isolate all common real roots in rational rectangles, 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 subresultant-based methods: this notation ignores polylogarithmic factors, where $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. We exploit recent advances on the complexity of univariate root isolation, and extend them to sign evaluation of bivariate polynomials over algebraic numbers, and real root counting for polynomials 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, system solvers from \synaps, and \maple libraries \funcinsulate and \functop, which compute curve topology. Our software is among the most robust, and its runtimes are comparable, or within a small constant factor, with respect to the \cc/\cpp libraries.
BibTeX:
@Article{det-jsc-2009,
author = {Dimitris~I. Diochnos and Ioannis~Z. Emiris and
Elias~P. Tsigaridas},
title = {On the asymptotic and practical complexity of
solving bivariate systems over the reals},
journal = jsc,
volume = 44,
number = 7,
pages = "818--835",
year = 2009,
note = {(Special issue on ISSAC 2007)},
abstract = " This paper is concerned with exact real solving of
well-constrained, bivariate polynomial systems. The
main problem is to isolate all common real roots in
rational rectangles, 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\-ant-based
methods: this notation ignores polylogarithmic
factors, where $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. We exploit recent advances
on the complexity of univariate root isolation, and
extend them to sign evaluation of bivariate
polynomials over algebraic numbers, and real root
counting for polynomials 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, system solvers from \synaps, and
\maple libraries \func{insulate} and \func{top},
which compute curve topology. Our software is among
the most robust, and its runtimes are comparable, or
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