Files:
Abstract:
We elaborate on a correspondence between the coefficients of a multivariate polynomial represented in the Bernstein basis and in a tensor-monomial basis, which leads to homography representations of polynomial functions, that use only integer arithmetic (in contrast to Bernstein basis) and are feasible over unbounded regions. Then, we study an algorithm to split this representation and we obtain a subdivision scheme for the domain of multivariate polynomial functions. This implies a new algorithm for real root isolation, MCF, that generalizes the Continued Fraction (CF) algorithm of univariate polynomials. A partial extension of Vincent's Theorem for multivariate polynomials is presented, which allows us to prove the termination of the algorithm. Bounding functions, projection and preconditioning are employed to speed up the scheme. The resulting isolation boxes have optimized rational coordinates, corresponding to the first terms of the continued fraction expansion of the real roots. Finally, we present new complexity bounds for a simplified version of the algorithm in the bit complexity model, and also bounds in the real RAM model for a family of subdivision algorithms in terms of the real condition number of the system. Examples computed with our C++ implementation illustrate the practical aspects of our method.
BibTeX:
@Article{mmt-tcs-2010,
author = {Angelos Mantzaflaris and Bernard Mourrain and Elias
P. Tsigaridas},
title = {On Continued Fraction Expansion of Real Roots of
Polynomial Systems, Complexity and Condition
Numbers},
journal = TCS,
volume = 412,
number = 22,
year = 2011,
pages = {2312-2330},
abstract = "We elaborate on a correspondence between the
coefficients of a multivariate polynomial
represented in the Bernstein basis and in a
tensor-monomial basis, which leads to homography
representations of polynomial functions, that use
only integer arithmetic (in contrast to Bernstein
basis) and are feasible over unbounded regions.
Then, we study an algorithm to split this
representation and we obtain a subdivision scheme
for the domain of multivariate polynomial functions.
This implies a new algorithm for real root
isolation, MCF, that generalizes the Continued
Fraction (CF) algorithm of univariate polynomials.
A partial extension of \emph{Vincent's Theorem} for
multivariate polynomials is presented, which allows
us to prove the termination of the algorithm.
Bounding functions, projection and preconditioning
are employed to speed up the scheme. The resulting
isolation boxes have optimized rational coordinates,
corresponding to the first terms of the
\emph{continued fraction expansion} of the real
roots. Finally, we present new complexity bounds
for a simplified version of the algorithm in the bit
complexity model, and also bounds in the real RAM
model for a family of subdivision algorithms in
terms of the real \emph{condition number} of the
system. Examples computed with our C++
implementation illustrate the practical aspects of
our method.",
url = "http://hal.inria.fr/inria-00530756",
}
Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02