Overdetermined systems of sparse polynomial equations
From MaRDI portal
Publication:2340503
Abstract: We show that, for a system of univariate polynomials given in sparse encoding, we can compute a single polynomial defining the same zero set, in time quasi-linear in the logarithm of the degree. In particular, it is possible to determine whether such a system of polynomials does have a zero in time quasi-linear in the logarithm of the degree. The underlying algorithm relies on a result of Bombieri and Zannier on multiplicatively dependent points in subvarieties of an algebraic torus. We also present the following conditional partial extension to the higher dimensional setting. Assume that the effective Zilber conjecture holds. Then, for a system of multivariate polynomials given in sparse encoding, we can compute a finite collection of complete intersections outside hypersurfaces that defines the same zero set, in time quasi-linear in the logarithm of the degree.
Recommendations
- Overdetermined Systems of Linear Equations
- Affine solution sets of sparse polynomial systems
- Positive solutions of sparse polynomial systems
- A Polyhedral Method for Solving Sparse Polynomial Systems
- Decomposable sparse polynomial systems
- Systems of linear equations with dense univariate polynomial coefficients
- Efficient algorithms for solving overdefined systems of multivariate polynomial equations
- Solving systems of linear algebraic equations of a special kind with sparse polynomial and numerical coefficients
- Overdetermined systems of equations on toric, spherical, and other algebraic varieties
- Elimination for generic sparse polynomial systems
Cites work
- scientific article; zbMATH DE number 435565 (Why is no real title available?)
- scientific article; zbMATH DE number 1264924 (Why is no real title available?)
- scientific article; zbMATH DE number 1936673 (Why is no real title available?)
- scientific article; zbMATH DE number 1981162 (Why is no real title available?)
- scientific article; zbMATH DE number 1467743 (Why is no real title available?)
- scientific article; zbMATH DE number 1402564 (Why is no real title available?)
- scientific article; zbMATH DE number 2247920 (Why is no real title available?)
- Algebraic curves and multiplicative equations.
- Anomalous Subvarieties—Structure Theorems and Applications
- Computing the torsion points of a variety defined by lacunary polynomials
- EXPONENTIAL SUMS EQUATIONS AND THE SCHANUEL CONJECTURE
- Exponential diophantine equations
- Irreducibility and greatest common divisor algorithms for sparse polynomials
- Lecture Notes on Diophantine Analysis
- On the Bounded Height Conjecture
- On the reducibility of polynomials and in particular of trinomials
- Relations de d\'ependance et intersections exceptionnelles (Dependence relations and exceptional intersections)
- Some problems of unlikely intersections in arithmetic and geometry. With appendixes by David Masser
- Sparse complex polynomials and polynomial reducibility
- The intersection of a curve with a union of translated codimension-two subgroups in a power of an elliptic curve
Cited in
(7)- Computing the multilinear factors of lacunary polynomials without heights
- Positive solutions of sparse polynomial systems
- Affine solution sets of sparse polynomial systems
- Overdetermined systems of equations on toric, spherical, and other algebraic varieties
- Zero testing and equation solving for sparse polynomials on rectangular domains
- Global residues for sparse polynomial systems
- Unlikely intersections and multiple roots of sparse polynomials
This page was built for publication: Overdetermined systems of sparse polynomial equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2340503)
