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

DSpace/Manakin Repository


Search DR-NTU

Advanced Search Subject Search


My Account

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

Show simple item record

dc.contributor.author Grigoriev, Dima.
dc.contributor.author Pasechnik, Dmitrii V.
dc.date.accessioned 2011-07-06T03:22:00Z
dc.date.available 2011-07-06T03:22:00Z
dc.date.copyright 2005
dc.date.issued 2011-07-06T03:22:00Z
dc.identifier.citation Grigoriev, D., & Pasechnik, D. V. (2005). Polynomial-time computing over quadratic maps I: sampling in real algebraic sets. Computational Complexity, 14, 20-52.
dc.identifier.uri http://hdl.handle.net/10220/6869
dc.description.abstract Given a quadratic map Q : Kn → Kk defined over a computable subring D of a real closed field K, and p ∈ D[Y1,..., Yk] of degree d we consider the zero set Z = Z(p(Q(X)),Kn) ⊆ Kn of p(Q(X1,..., Xn)) ∈ D[X1,..., Xn]. We present a procedure that com¬putes, in (dn)O(k) arithmetic operations in D, a set S of (real univariate representations of) sampling points in Kn 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 is only capable of deciding in nO(k2) operations the nonemptiness (rather than constructing sampling points) of the set Z in the case of p(Y ) = Σi Y i2 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.format.extent 34 p.
dc.language.iso en
dc.relation.ispartofseries Computational complexity
dc.rights © 2005 Birkhäuser Verlag AG, Basel. This is the author created version of a work that has been peer reviewed and accepted for publication by Computational Complexity, Birkhäuser Verlag AG, Basel. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at the following DOI: http://dx.doi.org/10.1007/s00037-005-0189-7.
dc.subject DRNTU::Science::Mathematics::Applied mathematics.
dc.title Polynomial-time computing over quadratic maps I : sampling in real algebraic sets.
dc.type Journal Article
dc.contributor.school School of Physical and Mathematical Sciences
dc.identifier.doi http://dx.doi.org/10.1007/s00037-005-0189-7
dc.description.version Accepted version

Files in this item

Files Size Format View

This item appears in the following Collection(s)

Show simple item record


Total views

All Items Views
Polynomial-time computing over quadratic maps I : sampling in real algebraic sets. 354

Total downloads

All Bitstreams Views

Top country downloads

Country Code Views
China 76
United States of America 69
Singapore 16
Unknown Country 4
United Kingdom 4

Top city downloads

city Views
Mountain View 45
Singapore 16
Southampton 4
Seattle 3
Beijing 2