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
- 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?)
- A Gröbner free alternative for polynomial system solving
- A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
- A homotopy for solving general polynomial systems that respects m- homogeneous structures
- 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
- 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 Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set and Applications
- 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
- 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 Numerical Solution of Systems of Polynomials Arising in Engineering and Science
- The complexity of partial derivatives
- The differential ideal \([P] : M^ \infty\).
Cited in
(11)- Effective coefficient asymptotics of multivariate rational functions via semi-numerical algorithms for polynomial systems
- Multilinear polynomial systems: root isolation and bit complexity
- On the bit complexity of polynomial system solving
- Solving parametric systems of polynomial equations over the reals through Hermite matrices
- Bit complexity for computing one point in each connected component of a smooth real algebraic set
- Message length effects for solving polynomial systems on a hypercube
- Computing critical points for invariant algebraic systems
- Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients
- Faster real root decision algorithm for symmetric polynomials
- Real root finding for low rank linear matrices
- Homotopy techniques for solving sparse column support determinantal polynomial systems
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)
