Workpackages

Algebraic Algorithms

Polynomial equations and systems are ubiquitous in sciences and engineering, since they are very powerful in modeling diverse phenomena and, on the other hand, have been extensively studied. WP1 focuses on solving such equations and such systems: these constitute the fundamental problems of computational algebra and of computational algebraic geometry, respectively. The complexity of these problems is often too high, hence the need for algorithms that exploit the structure of the given equation or system, leading to complexity bounds in terms of the intrinsic rather than then nominal hardness of the problem. Exploiting structure and, in particular, sparseness is the main original contribution of our approach, as it will be illustrated throughout WP1. Revealing the structure of the particular input is the key to such algorithms and complexity bounds. Structure can be multifarious and, indeed, ESPRESSO examines many different aspects.

In equation solving, we examine methods with good average-case complexity as opposed to worst case, thus providing a more realistic measure of cost. In a recent work [4], we obtained the first results for the separation bounds (the minimum distance between two roots) for some famous classes of random polynomials. The emphasis is on real solving, which is more relevant for applications. Therefore, an important ingredient concerns effective zero bounds, i.e. estimates of the minimum distance of the roots of a polynomial equation or system from zero. Zero bounds, as well as separation bounds, lie at the centerpiece of our approach. We will consider the average case separation bound of the complex roots. This will allow us to estimate the average complexity of methods other than Sturm sequences, namely those relying on Descartes’ rule and the continued fraction expansion [10]. Conversely, we will be working on improving the worst-case bounds for this algorithm, since it has led us to one of the fastest methods for real solving.

The complexity of real solving is in P but, since it lies at the inner loop of several algorithms, improved algorithms are of paramount importance. Recent years have seen a renewed interest in the theoretical and practical aspects of this problem, with the record complexity lying in O∗(d⁴L²), where d bounds the degree and L the coefficient bitsize, while polylog factors are ignored [3, 5]. Today, the main open question is to juxtapose this complexity with that of numerical computation, namely O∗(d²L), given the fact that current algebraic software is often competitive with numerical solvers [10].

In system solving, we follow sparse elimination to model polynomials by the (Newton) polytopes specified by their nonzero terms, then target algorithms whose complexity depends on the volume of these polytopes, as opposed to total degree [2, 7]. This line of work introduced the sparse resultant. The resultant is the most fundamental tool in variable elimination and leads to efficient system solving algorithms, but also appears in Grobner bases. Resultants reduce the solution of well-constrained systems of multivariate polynomials to an eigenproblem of a square matrix. An important aspect of structure is to reveal the structure of such matrices. We applied sparse elimination to improve upon Canny’s famous gap theorem [6]. We plan to improve the separation bounds of triangular and overdetermined polynomial systems, especially when we are only interested in isolated real roots, even when the zero-set has positive dimension. We shall generalize continued fractions to polynomial systems by dropping the assumption that all roots are of multiplicity one.

ESPRESSO develops computer algebra methods, focusing on two critical applications, both in modeling physical phenomena in the wide sense. In dessiminating our results and having an impact on these applications, a key element is the development of high-quality, public-domain software. The applications are chosen so as to include a domain that has already benefited from algebraic algorithms, including certain that exploit structure (WP2), and one where algebraic reasoning is a challenge that is supposed to open up new possibilities (WP3). In both fields, polynomials are able to model important questions. Moreover, most instances are concerned only with real roots, as opposed to complex roots, hence our methods exploiting structure should readily apply. Lastly, in both chosen areas, ESPRESSO members are among the respective field leaders.

Geometric Modeling

The first field of application concerns geometric modeling. This serves both as motivation and as a testbed for our ideas, algorithms, and implementations. The PI has an extensive experience in adapting algebraic tools to geometric problems and, since the area is scientifically mature, we expect to obtain tangible and practical results, with a visible impact in critical areas such as computer-aided industrial design, bioinformatics and computer-aided drug discovery, and nonlinear optimization. An important element of WP2 is the development of specialized effective, publicly available, algebraic software for geometric operations. Our work aspires to reduce the gap between classical computational, or algorithmic, geometry, an area with impressive theoretical progress in the past 20 years, and computer-aided geometric design, an area of high industrial impact. The area of interest is also known as nonlinear computational geometry, a field which wishes to extend the exact or certified methods of computational geometry from polyhedral and linear objects to curved, or nonlinear, objects.

Objectives:
– Robust modeling of complex shapes, such as molecular conformations, or complex curved shapes.
– Conversion between representations, e.g. from parametric to implicit and conversely.
– Simplification of representation in high dimensions, e.g. convex hulls of space curves, discriminants for describing conformations.
– Discretized approximations of complex shapes, e.g. by point clouds or piecewise linear functions.

Computational Game Theory

Our second application uses algebraic tools to better model stochastic games with the goal of studying and computing finite or infinite game equilibria. Game theory is an area of intensive growth but which has so far benefited very little from algebraic techniques. A notable exception is [8] by ESPRESSO members and co-workers. WP3 has an ambitious objective since it aims at enhancing computational game theory with an arsenal of algebraic tools adapted to the problems at hand. This contribution is quite original and emphasizes algorithmic results and the corresponding prototype implementations that shall illustrate the practicality of our methods. Specifically, we focus on zero-sum 2-player games and examine them under fictituous play so as to understand their rate of convergence; this is related to the deep question of computing in an approximate Nash equilibrium in P, with minimum approximation ratio [1, 9]. An important algebraic tool is linear programming and duality, which we plan to employ so as to develop procedures of learning to play. We aim at fast, complete and robust algorithms for computing the values of imperfect information stochastic games, using techniques from real algebraic geometry as well as polyhedral geometry. As is always the case with technology transfer, the use of algebraic tools requires a two-way effort of adapting the corresponding tools to game theoretic problems while, on the other hand, knowledge of the latter will guide our algebraic research.

Objectives:
– Enumeration of Nash equilibiria
– Convergence of zero-sum 2-player games and relation to linear programming.
– Complexity of imperfect information zero-sum 2-player stochastic games when the number of positions is not constant.
– Study of uniform strategies for stochastic games.