Session S34 - Symbolic and Numerical Computation with Polynomials

Wednesday, July 14, 11:00 ~ 11:30 UTC-3

A new algorithm for the equidimensional decomposition of affine varieties given by sparse polynomials

María Isabel Herrero

UBA - CONICET, Argentina   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

Any algebraic variety can be uniquely decomposed as a finite irredundant union of equidimensional varieties (which are called its equidimensional components). The different known algorithms that compute this decomposition characterize these components in different ways. For example, we can mention the representation of components via equations that define them, via parametric representations, and from the numerical algebraic geometry viewpoint, the representation of components can be done through finite sets of witness points that characterize them.

When considering the sparse structure of the given polynomials defining the original variety, that is, the monomials that appear with non-zero coefficients in these polynomials, algorithms with better performance can be designed. Following this approach, in a previous work with Gabriela Jeronimo and Juan Sabia, we presented a symbolic algorithm that describes the equidimensional decomposition by means of finite witness point supersets for varieties defined by sparse polynomials. This algorithm has a complexity that depends on geometric-combinatorial invariants associated with the set of supports of the polynomials. Unfortunately, the description it computes is precise for generic polynomials with prescribed monomial structure, but in particular cases, the sets of points describing a component may contain extra points from components of higher dimension.

In this talk we will present recent results improving our previous algorithm. We will show new theoretical results based on homotopic deformations that allowed us to design a symbolic algorithm to compute, for a variety given by arbitrary sparse polynomials, a representation of its equidimensional components by means of witness sets with no extra points. The algorithm uses a subroutine we developed that, given a finite set of points in the variety, determines for each point the equidimensional component of the highest dimension that contains it. As our previous algorithm, the complexity of this new procedure is polynomial in the same type of invariants associated with the supports.

Joint work with Gabriela Jeronimo (UBA - CONICET, Argentina) and Juan Sabia (UBA - CONICET, Argentina).

View abstract PDF