June 14, 2018
Similar papers 2
January 22, 2024
Geometry of sparse systems of polynomial equations (i.e. the ones with prescribed monomials and generic coefficients) is well studied in terms of their Newton polytopes. The results of this study are colloquially known as the Bernstein--Kouchnirenko--Khovanskii toolkit, and unfortunately are not applicable to many important systems, whose coefficients slightly fail to be generic. This for instance happens if some of the equations are obtained from another one by taking part...
December 26, 2008
The well-known Bernstein-Kushnirenko theorem from the theory of Newton polyhedra relates algebraic geometry and the theory of mixed volumes. Recently the authors have found a far-reaching generalization of this theorem to generic systems of algebraic equations on any quasi-projective variety. In the present note we review these results and their applications to algebraic geometry and convex geometry.
February 13, 2019
Let $E_1,\ldots,E_k$ be a collection of linear series on an algebraic variety $X$ over $\mathbb{C}$. That is, $E_i\subset H^0(X, \mathcal{L}_i)$ is a finite dimensional subspace of the space of regular sections of line bundles $ \mathcal{L}_i$. Such a collection is called overdetermined if the generic system \[ s_1 = \ldots = s_k = 0, \] with $s_i\in E_i$ does not have any roots on $X$. In this paper we study solvable systems which are given by an overdetermined collection of...
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 25, 2008
Given an affine variety X and a finite dimensional vector space of regular functions L on X, we associate a convex body to (X, L) such that its volume is responsible for the number of solutions of a generic system of functions from L. This is a far reaching generalization of usual theory of Newton polytopes (which is concerned with toric varieties). As applications we give new, simple and transparent proofs of some well-known theorems in both algebraic geometry (e.g. Hodge In...
May 2, 2014
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. For the problem of computing solution sets in the intersection of some coordinate planes, the direct application of a polyhed...
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 ...
October 25, 2005
We study the problem of counting the total number of affine solutions of a system of n binomials in n variables over an algebraically closed field of characteristic zero. We show that we may decide in polynomial time if that number is finite. We give a combinatorial formula for computing the total number of affine solutions (with or without multiplicity) from which we deduce that this counting problem is #P-complete. We discuss special cases in which this formula may be compu...
April 8, 2005
The main results of this paper interpret mixed volumes of lattice polytopes as mixed multiplicities of ideals and mixed multiplicities of ideals as Samuel's multiplicities. In particular, we can give a purely algebraic proof of Bernstein's theorem which asserts that the number of common zeros of a system of Laurent polynomial equations in the torus is bounded above by the mixed volume of their Newton polytopes.
August 15, 2023
In this paper we study a broad class of polynomial optimization problems whose constraints and objective functions exhibit sparsity patterns. We give two characterizations of the number of critical points to these problems, one as a mixed volume and one as an intersection product on a toric variety. As a corollary, we obtain a convex geometric interpretation of polar degrees, a classical invariant of algebraic varieties as well as Euclidean distance degrees. Furthermore, we p...