Polynomial-time computing over quadratic maps i: sampling in real algebraic sets
From MaRDI portal
(Redirected from Publication:1781114)
Abstract: Given a quadratic map Q : K^n -> K^k defined over a computable subring D of a real closed field K, and a polynomial p(Y_1,...,Y_k) of degree d, we consider the zero set Z=Z(p(Q(X)),K^n) of the polynomial p(Q(X_1,...,X_n)). We present a procedure that computes, in (dn)^O(k) arithmetic operations in D, a set S of (real univariate representations of) sampling points in K^n that intersects nontrivially each connected component of Z. As soon as k=o(n), this is faster than the standard methods that all have exponential dependence on n in the complexity. In particular, our procedure is polynomial-time for constant k. In contrast, the best previously known procedure (due to A.Barvinok) is only capable of deciding in n^O(k^2) operations the nonemptiness (rather than constructing sampling points) of the set Z in the case of p(Y)=sum_i Y_i^2 and homogeneous Q. A by-product of our procedure is a bound (dn)^O(k) on the number of connected components of Z. The procedure consists of exact symbolic computations in D and outputs vectors of algebraic numbers. It involves extending K by infinitesimals and subsequent limit computation by a novel procedure that utilizes knowledge of an explicit isomorphism between real algebraic sets.
Recommendations
- Numerically computing real points on algebraic sets
- scientific article; zbMATH DE number 2151204
- A baby step-giant step roadmap algorithm for general algebraic sets
- On computing a set of points meeting every cell defined by a family of polynomials on a variety
- Computing the real isolated points of an algebraic hypersurface
Cited in
(19)- A sharper estimate on the Betti numbers of sets defined by quadratic inequalities
- When a system of real quadratic equations has a solution
- Deciding Koopman's qualitative probability
- Quadratic Maps Are Hard to Sample
- A note on polynomial solvability of the CDT problem
- A two-variable approach to the two-trust-region subproblem
- Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time
- On the equivalence of two post-quantum cryptographic families
- On obtaining the convex hull of quadratic inequalities via aggregations
- The inverse moment problem for convex polytopes
- On projections of semi-algebraic sets defined by few quadratic inequalities
- Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials
- On the reduction of multivariate quadratic systems to best rank-1 approximation of three-way tensors
- Integrating products of quadratic forms
- An evolutionary approach to the automatic classification of automorphisms of lower-dimensional Lie algebras
- Narrowing the difficulty gap for the Celis-Dennis-Tapia problem
- Geodesic diameter of sets defined by few quadratic equations and inequalities
- Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials
- Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
This page was built for publication: Polynomial-time computing over quadratic maps i: sampling in real algebraic sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1781114)
