Abstract. A classical method to compute with sparse polynomials is to homogenize them with respect to Newton polytopes, regarding them as homogeneous elements of Cartier degrees in the Cox ring of a projective toric variety. In this talk, we investigate subvarieties defined by generic polynomial systems in the Cox ring when the degrees are non-necessarily Cartier, with a view towards identifying alternative toric homogenizations that are suitable for practical computations. Joint work with Matías Bender.

Abstract. In this talk, I will present the connections between chordal graphs from graph theory and triangular decomposition in top-down style from symbolic computation, including the underlying theories, algorithms, and applications in biology. Viewing triangular decomposition in top-down style as polynomial generalization of Gaussian elimination, we show that all the polynomial sets, including all the computed triangular sets, appearing in several typical top-down algorithms for triangular decomposition have associated graphs which are subgraphs of the chordal graph of the input polynomial set. These theoretical results can be interpreted as “triangular decomposition in top-down style preserves chordality” and are further used to design sparse triangular decomposition for polynomial sets which are sparse with respect to their variables. Sparse triangular decomposition is shown to be more efficient than ordinary one experimentally, and its application on computing equilibria of biological dynamic systems will also be reported. This talk is based on the joint work with Yang Bai, Jiahua Lai, and Wenwen Ju.

abstract_moreno-maza.pdf

Abstract. Multiple classical problems in the formal verification of programs such as reachability, termination, and template-based synthesis can be reduced to solving polynomial systems of equations. In this talk, I will describe the primary objects and these connections. In particular, I will show how the algebraic and geometric techniques can be applied, enhancing the scalability and completeness for such problems.

Abstract. The main object of study in the (algebraic) theory of reaction networks is the solution se of a system of parametric polynomial equations in the positive orthant. This system consists of polynomials with fixed support, the coefficients are linear in the parameters, but there might be some (proportionality) dependencies among the coefficients. The questions of interest concern properties of this system, and of its intersection with a family of parallel linear subspaces of complementary dimension. In this case, of relevance is to determine the possible number of zeros the system has when the parameters vary. In this talk I will introduce the framework and the families of polynomial systems under study in full generality, and having the reaction networks as the main application. I will proceed to discuss recent results addressing the expected dimension of the solution sets and on how to decide whether the solution set admits a toric parametrization for all parameter values. The latter is relevant for the problem of counting solutions, and this connection will also be explained in the talk.

Abstract. In this talk, we first provide a comprehensive definition of closed n-linkages and explain their mobility, typically denoted as n-6. We then focus on the intriguing subset of closed n-linkages with a mobility higher than n-6, known as paradoxical linkages. Based on the powerful tools of Bond Theory and the freezing technique, we present a thorough classification of n-linkages with a mobility of n-4 or higher, incorporating revolute, prismatic, or helical joints. Additionally, we explicitly derive strong necessary conditions for nR-linkages with a mobility of n-5. Utilizing these necessary conditions, we explore and discuss possible polynomial systems that arise in paradoxical 6R linkages.

Abstract. Numerical algebraic geometry provides a collection of algorithms for computing and analyzing solution sets of polynomial systems. This talk will discuss new techniques that have been developed in numerical algebraic geometry for focusing on real solution sets of polynomial systems. Several applications of these techniques will be presented such as computing smooth points on algebraic sets, approximate synthesis of mechanisms, and path planning for output mode switching.

Abstract. We develop a new method that improves the efficiency of equation-by-equation homotopy continuation methods for solving polynomial systems. Our method is based on a novel geometric construction and reduces the total number of homotopy paths that must be numerically continued. These improvements may be applied to the basic algorithms of numerical algebraic geometry in the settings of both projective and multiprojective varieties. (This is joint work with T. Duff and J. I. Rodriguez.)

Abstract. Polynomial optimization deals with optimizing a polynomial function over a feasible region defined by polynomial inequalities, thus modeling a broad range of hard nonlinear nonconvex optimization problems. Hierarchies of tractable semidefinite relaxations have been introduced that are based on using sums of squares of polynomials as a ``proxy” for global nonnegativity. These hierarchies give bounds on the global minimum of the original problem with asymptotic convergence (under a minor compactness assumption). In this lecture we discuss recent results on the performance analysis of these hierarchies and related effective degree bounds for dedicated sums of squares representations of positive polynomials on some classes of compact semi-algebraic sets (including the hypercube, the sphere or the ball).

Abstract. Finding the common roots of a set of polynomial equations is a problem that appears in many contexts and applications. Standard approaches for solving this difficult question, such as Grobner bases, border basis, triangular sets, etc. are based on polynomial reductions but their instability against numerical approximations can be critical. In this talk, we will describe a dual approach which focuses on linear functionals vanishing at the roots. We will review the properties of Truncated Normal Forms, the connexion with classical computer algebra approaches and resultants. We will also detail the dual approach in the context of optimisation problems and for analysing isolated singularities. Examples from geometric modeling, robotics and tensor decomposition will illustrate the numerical behavior of these dual methods.

Abstract. In this work in progress with Lorenzo Baldi and Bernard Mourrain, we extend previous results on univariate rational sums of squares, obtained with Bernard and Agnes Szanto, to the case of a non-negative rational polynomial on a basic zero-dimensional semi-algebraic set defined by rational polynomials.

Abstract. We describe a new algorithm for computing Whitney stratifications of complex projective varieties. The main ingredients are (a) an algebraic criterion, due to Lê and Teissier, which reformulates Whitney regularity in terms of conormal spaces and maps, and (b) a new interpretation of this conormal criterion via ideal saturations, which can be practically implemented on a computer. We show that this algorithm improves upon the existing state of the art by several orders of magnitude, even for relatively small input varieties. This is joint work with Vidit Nanda (Oxford).

Abstract. The Vandermonde map is the polynomial map given by the power-sum polynomials. We study the geometry of the image of the nonnegative orthant under under this map and focus on the limit as the number of variables approaches infinity. We will show, the geometry of this limit is the key to new undecidability results in nonnegativity of symmetric polynomials and deciding validity of trace inequalities in linear algebra.

Abstract. The tasks of designing innovative mathematical software and of solving complex research problems using computational methods are strongly mutually dependent. Developing a new generation of algorithms to considerably push the computational boundaries of nonlinear algebra, notably addressing polynomial system solving, is thus envitable. One important task of this process is to no longer use Gröbner bases only as a black box in higher level algorthms, but to optimize their computation with the geometric context in mind. In this talk, we will illustrate this idea by presenting a new algorithm for computing Gröbner bases of saturated polynomial ideals. Moreover, we introduce msolve, an open source software package build to provide this new generation of efficient and optimized algorithms for the community. The contents of this talk are based on joint work with Jérémy Berthomieu and Mohab Safey El Din.