Section: New Results

Symbolic-Numeric Analysis

A Subdivision Method for Computing Nearest Gcd with Certification

Participants : André Galligo, Bernard Mourrain.

A new subdivision method for computing the nearest univariate gcd is described and analyzed in [24] . It is based on an exclusion test and an inclusion test. The exclusion test in a cell exploits Taylor expansion of the polynomial at the center of the cell. The inclusion test uses Smale's alpha-theorems to certify the existence and unicity of a solution in a cell. Under the condition of simple roots for the distance minimization problem, we analyze the complexity of the algorithm in terms of a condition number, which is the inverse of the distance to the set of degenerate systems. We report on some experimentation on representative examples to illustrate the behavior of the algorithm.

This is a joint work with Guillaume Chèze and Jean-Claude Yakoubsohn (University Paul-Sabatier, Toulouse).

An Adapted Version of the Bentley-Ottmann Algorithm for Invariants of Plane Curves Singularities

Participant : Bernard Mourrain.

In [34] , we report on an adapted version of the Bentley-Ottmann algorithm for computing all the intersection points among the edges of the projection of a three-dimensional graph. This graph is given as a set of vertices together with their space Euclidean coordinates, and a set of edges connecting them. More precisely, the three-dimensional graph represents the approximation of a closed and smooth implicitly defined space algebraic curve, that allows us a simplified treatment of the events encountered in the Bentley-Ottmann algorithm. As applications, we use the adapted algorithm to compute invariants for each singularity of a plane complex algebraic curve, i.e. the Alexander polynomial, the Milnor number, the delta-invariant, etc.

This is a joint work with Madalina Hodorog and Joseph Schicho, from RICAM, Linz, Austria.

Virtual Roots of a Real Polynomial and Fractional Derivatives

Participant : André Galligo.

After the works of Gonzales-Vega, Lombardi, Mahé, and Coste, Lajous, Lombardi, Roy, we consider the virtual roots of a univariate polynomial $f$ with real coefficients. Using fractional derivatives, we associate to $f$ a bivariate polynomial $P_f(x,t)$ depending on the choice of an origin $a$, then two type of plan curves we call the FDcurve and stem of $f$. We show, in the generic case, how to locate the virtual roots of $f$ on the Budan table and on each of these curves. The paper [32] is illustrated with examples and pictures computed with the computer algebra system Maple. It is a joint work with Daniel Bembe.

Computing monodromy via continuation methods on random Riemann surfaces

Participant : André Galligo.

In [25] , we consider a Riemann surface $X$ defined by a polynomial $f(x,y)$ of degree $d$, whose coefficients are chosen randomly. Hence, we can suppose that $X$ is smooth, that the discriminant $\delta \left(x\right)$ of $f$ has $d\left(d-1\right)$ simple roots $\Delta$ and that $\delta \left(0\right)\ne 0$, i.e. the corresponding fiber has $d$ distinct points $\{y_1,\dots ,y_d\}$. When we lift a loop $0\in \gamma \subset C-\Delta$ by a continuation method, we get $d$ paths in $X$ connecting $\{y_1,\dots ,y_d\}$, hence defining a permutation of that set. This is called monodromy.

Here we present experimentations in Maple to get statistics on the distribution of transpositions corresponding to loops around each point of $\Delta$. Multiplying families of “neighbor” transpositions, we construct permutations and the subgroups of the symmetric group they generate. This allows us to establish and study experimentally two conjectures on the distribution of these transpositions and on transitivity of the generated subgroups.

Assuming that these two conjectures are true, we develop tools allowing fast probabilistic algorithms for absolute multivariate polynomial factorization, under the hypothesis that the factors behave like random polynomials whose coefficients follow uniform distributions. It is a joint work with Adrien Poteaux (University of Lille).