Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
From MaRDI portal
Abstract: Multi-homogeneous polynomial systems arise in many applications. We provide bit complexity estimates for solving them which, up to a few extra other factors, are quadratic in the number of solutions and linear in the height of the input system under some genericity assumptions. The assumptions essentially imply that the Jacobian matrix of the system under study has maximal rank at the solution set and that this solution set if finite. The algorithm is probabilistic and a probability analysis is provided. Next, we apply these results to the problem of optimizing a linear map on the real trace of an algebraic set. Under some genericity assumptions, we provide bit complexity estimates for solving this polynomial minimization problem.
Recommendations
Cites work
- A Gröbner free alternative for polynomial system solving
- A homotopy for solving general polynomial systems that respects m- homogeneous structures
- A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
- A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
- Algorithms in real algebraic geometry
- An algebraically closed field
- Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions
- Computing multihomogeneous resultants using straight-line programs
- Computing parametric geometric resolutions
- Critical points and Gröbner bases: the unmixed case
- Deformation techniques for sparse systems
- Exact algorithms for linear matrix inequalities
- Feasibility testing for systems of real quadratic equations
- Finding at least one point in each connected component of a real algebraic set defined by a single equation
- Generalized polar varieties: geometry and algorithms
- Heights of varieties in multiprojective spaces and arithmetic nullstellensätze
- scientific article; zbMATH DE number 4132308 (Why is no real title available?)
- scientific article; zbMATH DE number 3903874 (Why is no real title available?)
- scientific article; zbMATH DE number 3554399 (Why is no real title available?)
- scientific article; zbMATH DE number 3563286 (Why is no real title available?)
- scientific article; zbMATH DE number 704831 (Why is no real title available?)
- scientific article; zbMATH DE number 1057749 (Why is no real title available?)
- scientific article; zbMATH DE number 1936673 (Why is no real title available?)
- scientific article; zbMATH DE number 2151204 (Why is no real title available?)
- scientific article; zbMATH DE number 939802 (Why is no real title available?)
- scientific article; zbMATH DE number 3196341 (Why is no real title available?)
- Intrinsic complexity estimates in polynomial optimization
- Le rôle des structures de données dans les problèmes d'élimination
- Lifting techniques for triangular decompositions
- On the bit complexity of solving bilinear polynomial systems
- On the complexity of computing critical points with Gröbner bases
- On the complexity of the multivariate resultant
- On the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set and Applications
- Polar varieties and efficient real elimination
- Polar varieties, real equation solving, and data structures: the hypersurface case
- Polynomial-time computing over quadratic maps i: sampling in real algebraic sets
- Powers of tensors and fast matrix multiplication
- Sharp estimates for the arithmetic Nullstellensatz
- Solving zero-dimensional systems through the rational univariate representation
- Straight-line programs in geometric elimination theory
- Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
- The complexity of partial derivatives
- The differential ideal \([P] : M^ \infty\).
- The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
Cited in
(18)- Message length effects for solving polynomial systems on a hypercube
- On the bit complexity of polynomial system solving
- Homotopy techniques for solving sparse column support determinantal polynomial systems
- Multilinear polynomial systems: root isolation and bit complexity
- Bit complexity for computing one point in each connected component of a smooth real algebraic set
- Computing critical points for invariant algebraic systems
- Solving parametric systems of polynomial equations over the reals through Hermite matrices
- Real root finding for low rank linear matrices
- Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems
- Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients
- Faster real root decision algorithm for symmetric polynomials
- Rigorous analytic combinatorics in several variables in SageMath
- On spectral and nuclear norms of order three tensors with one fixed dimension
- Probabilistic algorithm for computing all local minimizers of Morse functions on a compact domain
- Some applications of Chinese remainder theorem codes with error-correction
- Computing roadmaps in unbounded smooth real algebraic sets. II: Algorithm and complexity
- Refined bit complexity for the computation of at least one point per connected component of a smooth complete intersection real algebraic set
- Solving parametric linear matrix inequalities
This page was built for publication: Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1690788)
