May 19, 2022
Solving systems of polynomial equations is a central problem in nonlinear and computational algebra. Since Buchberger's algorithm for computing Gr\"obner bases in the 60s, there has been a lot of progress in this domain. Moreover, these equations have been employed to model and solve problems from diverse disciplines such as biology, cryptography, and robotics. Currently, we have a good understanding of how to solve generic systems from a theoretical and algorithmic point of view. However, polynomial equations encountered in practice are usually structured, and so many properties and results about generic systems do not apply to them. For this reason, a common trend in the last decades has been to develop mathematical and algorithmic frameworks to exploit specific structures of systems of polynomials. Arguably, the most common structure is sparsity; that is, the polynomials of the systems only involve a few monomials. Since Bernstein, Khovanskii, and Kushnirenko's work on the expected number of solutions of sparse systems, toric geometry has been the default mathematical framework to employ sparsity. In particular, it is the crux of the matter behind the extension of classical tools to systems, such as resultant computations, homotopy continuation methods, and most recently, Gr\"obner bases. In this work, we will review these classical tools, their extensions, and recent progress in exploiting sparsity for solving polynomial systems. This manuscript complements its homonymous tutorial presented at the conference ISSAC 2022.
Similar papers 1
January 27, 2012
Sparse (or toric) elimination exploits the structure of polynomials by measuring their complexity in terms of Newton polytopes instead of total degree. The sparse, or Newton, resultant generalizes the classical homogeneous resultant and its degree is a function of the mixed volumes of the Newton polytopes. We sketch the sparse resultant constructions of Canny and Emiris and show how they reduce the problem of root-finding to an eigenproblem. A novel method for achieving this ...
February 1, 2019
Gr{\"o}bner bases is one the most powerful tools in algorithmic non-linear algebra. Their computation is an intrinsically hard problem with a 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 in...
February 28, 2014
Toric (or sparse) elimination theory is a framework developped during the last decades to exploit monomial structures in systems of Laurent polynomials. Roughly speaking, this amounts to computing in a \emph{semigroup algebra}, \emph{i.e.} an algebra generated by a subset of Laurent monomials. In order to solve symbolically sparse systems, we introduce \emph{sparse Gr\"obner bases}, an analog of classical Gr\"obner bases for semigroup algebras, and we propose sparse variants ...
February 8, 1997
This paper reexamines univariate reduction from a toric geometric point of view. We begin by constructing a binomial variant of the $u$-resultant and then retailor the generalized characteristic polynomial to fully exploit sparsity in the monomial structure of any given polynomial system. We thus obtain a fast new algorithm for univariate reduction and a better understanding of the underlying projections. As a corollary, we show that a refinement of Hilbert's Tenth Problem is...
October 15, 2013
To compute solutions of sparse polynomial systems efficiently we have to exploit the structure of their Newton polytopes. While the application of polyhedral methods naturally excludes solutions with zero components, an irreducible decomposition of a variety is typically understood in affine space, including also those components with zero coordinates. We present a polyhedral method to compute all affine solution sets of a polynomial system. The method enumerates all factors ...
February 8, 1997
We illustrate an efficient new method for handling polynomial systems with degenerate solution sets. In particular, a corollary of our techniques is a new algorithm to find an isolated point in every excess component of the zero set (over an algebraically closed field) of any $n$ by $n$ system of polynomial equations. Since we use the sparse resultant, we thus obtain complexity bounds (for converting any input polynomial system into a multilinear factorization problem) which ...
October 13, 2017
It has by now become a standard approach to use the theory of sparse (or toric) elimination, based on the Newton polytope of a polynomial, in order to reveal and exploit the structure of algebraic systems. This talk surveys compact formulae, including older and recent results, in sparse elimination. We start with root bounds and juxtapose two recent formulae: a generating function of the m-B{\'e}zout bound and a closed-form expression for the mixed volume by means of a matrix...
April 22, 2013
Polynomial system solving is a classical problem in mathematics with a wide range of applications. This makes its complexity a fundamental problem in computer science. Depending on the context, solving has different meanings. In order to stick to the most general case, we consider a representation of the solutions from which one can easily recover the exact solutions or a certified approximation of them. Under generic assumption, such a representation is given by the lexicogr...
February 27, 2022
This paper is concerned with linear algebra based methods for solving exactly polynomial systems through so-called Gr\"obner bases, which allow one to compute modulo the polynomial ideal generated by the input equations. This is a topical issue in non-linear algebra and more broadly in computational mathematics because of its numerous applications in engineering and computing sciences. Such applications often require geometric computing features such as representing the closu...
May 9, 2018
One of the biggest open problems in computational algebra is the design of efficient algorithms for Gr{\"o}bner basis computations that take into account the sparsity of the input polynomials. We can perform such computations in the case of unmixed polynomial systems, that is systems with polynomials having the same support, using the approach of Faug{\`e}re, Spaenlehauer, and Svartz [ISSAC'14]. We present two algorithms for sparse Gr{\"o}bner bases computations for mixed sys...