Conference Agenda

Modeling real-world systems or processes in areas such as control theory, geometric modeling, biochemistry, coding theory, cryptology, and so on, almost certainly involves non-linear equations. Higher degree equations are the first step away from linear models. Available tools for recovering their solutions range from numerical methods such as Newton-Raphson, homotopy continuation algorithms, subdivision-based solvers, to symbolic tools such as Groebner bases, border bases, characteristic sets and multivariate resultants. There is continuous progress in combining symbolic methods and numerical solving, in order to devise new algorithms with varying blends of exactness, stability and robustness as well as computational complexity, that are tailored for different applications. Among the challenges which occur in the process is reliable root isolation, certification and approximation, treatment of singular solutions, the exploitation of structure coming from specific applications as well as efficient interpolation.
The mini-symposium will host presentations related to state-of-the-art solution strategies for these problems, theoretical and algorithmic advances as well as emerging application areas.

Multivariate resultant matrices characterize the roots of a polynomial system and reduce their computation to an eigenvalue problem. However, determinantal formulas (i.e. without extraneous factors) for the resultant do not exist for arbitrary systems. They have been constructed mostly for unmixed systems, that is, systems of polynomial equations with a common Newton polytope of special structure. In this talk we derive determinantal formulations for the multivariate resultant of structured systems with distinct supports per equation. We focus on mixed multilinear polynomial systems, that is multilinear systems with different supports per equation. These systems have applications to the Multiparameter Eigenvalue Problem (MEP).

The Rational Interpolation Problem is an extension of the classical Polynomial Interpolation one, and there are several approaches to it: Euclidean algorithm, Linear Algebra with structured matrices, barycentric coordinates, orthogonal polynomials, computation of syzygies,.... We will review some of these methods along with some recent bounds in the complexity of their computation.

Gröbner bases are one the most powerful tools in algorithmic non-linear algebra. Their computation is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. For example, several problems in computer-aided design, robotics, vision, biology, kinematics, cryptography, and optimization involve sparse systems where the input polynomials have a few non-zero terms. An approach to exploit sparsity is to embed the systems in a semigroup algebra and to compute Gröbner bases over this algebra. Prior to our work, the algorithms that follow this approach benefited from the sparsity only in the case where all the polynomials have the same sparsity structure, that is the same Newton polytope. In this talk, I will present the first algorithm that overcomes this restriction. Under regularity assumptions, it performs no redundant computations. Further, I will use it to compute Gröbner basis in the standard algebra and solve sparse polynomials systems over the torus. The complexity of the algorithm depends on the Newton polytopes and it is similar to the complexity of the solving techniques involving the sparse resultant. Hence, this algorithm closes a 25-years gap between the strategies to solve systems using resultants and Gröbner bases. Additionally, for particular families of sparse systems, I will use the multigraded Castelnuovo-Mumford regularity to improve the complexity bounds.

Given an ideal I in a polynomial ring K[x_1, x_2, ... ,x_n], let its i-th elimination ideal be the ideal I_i= I cap K[x_1, x_2, ..., x_{n-i}]. The standard method for computing elimination ideals is by computing the Groebner basis G for I with respect to an elimination order and due to the elimination property of Groebner bases, the Groebner basis of I_i is G cap K[x_1, x_2, ..., x_{n-i}]. In this work we are interested in computing the i-th elimination ideal, without computing G, the Groebner basis of I, first. We do that by using the resultant system. The resultant system, introduced in van der Waerden's Modern Algebra, is a polynomial system having the properties we expect from a resultant. The resultant system contains a large number of polynomials, and thus it is not computationally efficient. We present an analysis of how we can improve the computation of the resultant system. Elimination ideals is a useful tool when dealing with parametric polynomial systems. Such systems often appear in applications and it was one of our original motivations, especially applications in combinatorics and motion planning.