Polynomial-time computing over quadratic maps i: sampling in real algebraic sets

DOI10.1007/S00037-005-0189-7zbMATH Open1082.14065DBLPjournals/cc/GrigorievP05arXivcs/0403008OpenAlexW3100802811WikidataQ56874379 ScholiaQ56874379MaRDI QIDQ1781114FDOQ1781114

Authors: Dima Grigoriev, Dmitrii V. Pasechnik 

Publication date: 16 June 2005

Published in: Computational Complexity (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cs/0403008

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

zbMATH Keywords

complexitysymbolic computationinfinitesimal deformationsemialgebraic setquadratic mapunivariate representation

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Semialgebraic sets and related spaces (14P10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Cited In (19)

• An evolutionary approach to the automatic classification of automorphisms of lower-dimensional Lie algebras
• Quadratic Maps Are Hard to Sample
• A sharper estimate on the Betti numbers of sets defined by quadratic inequalities
• Deciding Koopman's qualitative probability
• The inverse moment problem for convex polytopes
• Narrowing the difficulty gap for the Celis-Dennis-Tapia problem
• On obtaining the convex hull of quadratic inequalities via aggregations
• 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
• When a system of real quadratic equations has a solution
• Geodesic diameter of sets defined by few quadratic equations and inequalities
• On the reduction of multivariate quadratic systems to best rank-1 approximation of three-way tensors
• Integrating products of quadratic forms
• Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time
• A note on polynomial solvability of the CDT problem
• A two-variable approach to the two-trust-region subproblem
• On the equivalence of two post-quantum cryptographic families
• Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials
• On projections of semi-algebraic sets defined by few quadratic inequalities

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)