Search

International audience; We present an algorithm based on local generic position (LGP) to isolate the complex or real roots and their multiplicities of a zero-dimensional triangular polynomial system. The Boolean complexity of the algorithm for computing the real roots is single exponential: $\tilde{\mathcal {O}}_B(N^{n^2})$, where $N=\max\{d,\tau\}$, $d$ and $\tau$, is the degree and the maximum coefficient bitsize of the polynomials, respectively, and $n$ is the number of variables.

The study of (minimally) rigid graphs is motivated by numerous applications, mostly in robotics and bioinformatics. A major open problem concerns the number of embeddings of such graphs, up to rigid motions, in Euclidean space. We capture embeddability by polynomial systems with suitable structure, so that their mixed volume, which bounds the number of common roots, to yield interesting upper bounds on the number of embeddings. We focus on ${\mathbb R}^2$ and ${\mathbb R}^3$, where Laman graphs and 1-skeleta of convex simplicial polyhedra, respectively, admit inductive Henneberg constructions. We establish the first general lower bound in ${\mathbb R}^3$ of about 2.52n, where n denotes the number of vertices. Moreover, our implementation yields upper bounds for n≤10 in ${\mathbb R}^2$ and ${\mathbb R}^3$, which reduce the existing gaps, and tight bounds up to n=7 in ${\mathbb R}^3$.

Solving polynomials and performing operations with real algebraic numbers are critical issues in geometric computing, in particular when dealing with curved objects. Moreover, the real roots need to be computed in a certified way in order to avoid possible inconsistency in geometric algorithms. Developing efficient solutions for this problem is thus an important issue for the development of libraries of computational geometry algorithms and, in particular, for the state-of-the-art (open source) cgal library. We present a cgal-based univariate algebraic kernel, which provides certified real-root isolation of univariate polynomials with integer coefficients and standard functionalities such as basic arithmetic operations, greatest common divisor (gcd) and square-free factorization, as well as comparison and sign evaluations of real algebraic numbers. We compare our kernel with other comparable kernels, demonstrating the efficiency of our approach. Our experiments are performed on large data sets including polynomials of high degree (up to 2 000) and with very large coefficients (up to 25 000 bits per coefficient). We also address the problem of computing arrangements of x-monotone polynomial curves. We apply our kernel to this problem and demonstrate its efficiency compared to previous solutions available in cgal. We also present the first bit-complexity analysis of the standard sweep-line algorithm for this problem.

We present algorithmic, complexity and implementation results concerning real root isolation of a polynomial of degree d, with integer coefficients of bit size ≤ ?, using Sturm (-Habicht) sequences and the Bernstein subdivision solver. In particular, we unify and simplify the analysis of both methods and we give an asymptotic complexity bound of $\mathcal{\tilde O}_B(d^4 \tau^2)$. This matches the best known bounds for binary subdivision solvers. Moreover, we generalize this to cover the non square-free polynomials and show that within the same complexity we can also compute the multiplicities of the roots. We also consider algorithms for sign evaluation, comparison of real algebraic numbers and simultaneous inequalities, and we improve the known bounds at least by a factor of d. Finally, we present our C++ implementation in synaps and some preliminary experiments on various data sets.

We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued fraction expansion of real numbers. We improve the previously known bound by a factor of d T, where d is the polynomial degree and T bounds the coefficient bitsize, thus matching the current record complexity for real root isolation by exact methods. Namely, the complexity bound is O˜B(d4T2) using a standard bound on the expected bitsize of the integers in the continued fraction expansion. We show how to compute the multiplicities within the same complexity and extend the algorithm to non square-free polynomials. Finally, we present an efficient open-source C++ implementation in the algebraic library synaps, and illustrate its efficiency as compared to other available software. We use polynomials with coefficient bitsize up to 8000 and degree up to 1000.

A relatively recent area of study in geometric modelling concerns toric Bezier patches. In this line of work, several questions reduce to testing whether a given convex lattice polygon can be decomposed into a Minkowski sum of two such polygons and, if so, to finding one or all such decompositions. Other motivations for this problem include sparse resultant computation, especially for the implicitization of parametric surfaces, and factorization of bivariate polynomials. Particularly relevant for geometric modelling are decompositions where at least one summand has a small number of edges. We study the complexity of Minkowski decomposition and propose efficient algorithms for the case of constant-size summands. We have implemented these algorithms and illustrate them by various experiments with random lattice polygons and on all convex lattice polygons with zero or one interior lattice points. We also express the general problem by means of standard and well-studied problems in combinatorial optimization. This leads to an improvement in asymptotic complexity and, eventually, to efficient randomized algorithms and implementations.

We propose exact, complete and efficient methods for 2 problems: First, the real solving of systems of two bivariate rational polynomials of arbitrary degree. This means isolating all common real solutions in rational rectangles and calculating the respective multiplicities. Second, the computation of the sign of bivariate polynomials evaluated at two algebraic numbers of arbitrary degree. Our main motivation comes from nonlinear computational geometry and computer-aided design, where bivariate polynomials lie at the inner loop of many algorithms. The methods employed are based on Sturm-Habicht sequences, univariate resultants and rational univariate representation. We have implemented them very carefully, using advanced object-oriented programming techniques, so as to achieve high practical performance. The algorithms are integrated in the public-domain C++ software library synaps, and their efficiency is illustrated by 9 experiments against existing implementations. Our code is faster in most cases; sometimes it is even faster than numerical approaches.

We study polynomials of degree up to 4 over the rationals or a computable real subfield. Our motivation comes from the need to evaluate predicates in nonlinear computational geometry efficiently and exactly. We show a new method to compare real algebraic numbers by precomputing generalized Sturm sequences, thus avoiding iterative methods; the method, moreover handles all degenerate cases. Our first contribution is the determination of rational isolating points, as functions of the coefficients, between any pair of real roots. Our second contribution is to exploit invariants and Bezoutian subexpressions in writing the sequences, in order to reduce bit complexity. The degree of the tested quantities in the input coefficients is optimal for degree up to 3, and for degree 4 in certain cases. Our methods readily apply to real solving of pairs of quadratic equations, and to sign determination of polynomials over algebraic numbers of degree up to 4. Our third contribution is an implementation in a new module of library synaps v2.1. It improves significantly upon the efficiency of certain publicly available implementations: Rioboo’s approach on axiom, the package of Guibas-Karavelas-Russel [11], and core v1.6, maple v9, and synaps v2.0. Some existing limited tests had shown that it is faster than commercial library leda v4.5 for quadratic algebraic numbers.