Polynomial-time computing over quadratic maps I: sampling in real algebraic sets
| dc.creator | Grigoriev, Dima | |
| dc.creator | Pasechnik, Dmitrii V. | |
| dc.date | 2004-03-06 | |
| dc.date | 2004-12-31 | |
| dc.date.accessioned | 2026-07-07T03:20:58Z | |
| dc.date.available | 2026-07-07T03:20:58Z | |
| dc.description | 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. | |
| dc.description | 34 pages, LaTeX (Computational Complexity (cc.cls) class used); updated version, to appear in Comp. Complexity | |
| dc.identifier | https://arxiv.org/abs/cs/0403008 | |
| dc.identifier | http://arxiv.org/abs/cs/0403008 | |
| dc.identifier | Computational Complexity 14(2005) 20-52 | |
| dc.identifier | doi:10.1007/s00037-005-0189-7 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32027 | |
| dc.subject | Symbolic Computation | |
| dc.subject | Computational Geometry | |
| dc.subject | Algebraic Geometry | |
| dc.subject | I.1.2; G.1.5 | |
| dc.title | Polynomial-time computing over quadratic maps I: sampling in real algebraic sets | |
| dc.type | text |