mirage

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

DSpace/Manakin Repository

 

Search DR-NTU


Advanced Search Subject Search

Browse

My Account

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

Show full item record

Title: Polynomial-time computing over quadratic maps I : sampling in real algebraic sets.
Author: Grigoriev, Dima.; Pasechnik, Dmitrii V.
Copyright year: 2005
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.
Subject: DRNTU::Science::Mathematics::Applied mathematics.
Type: Journal Article
Series/ Journal Title: Computational complexity
School: School of Physical and Mathematical Sciences
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.
Version: Accepted version

Files in this item

Files Size Format View
12. POLYNOMIAL-TIME COMPUTING OVER.pdf 407.5Kb PDF View/Open
   

DOI Query

- Get published version (via Digital Object Identifier)
   

This item appears in the following Collection(s)

Show full item record

Statistics

Total views

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

Total downloads

All Bitstreams Views
12. POLYNOMIAL-TIME COMPUTING OVER.pdf 159

Top country downloads

Country Code Views
China 72
United States of America 51
Singapore 16
Unknown Country 4
United Kingdom 4

Top city downloads

city Views
Mountain View 37
Singapore 16
Southampton 4
Seattle 3
Ann Arbor 1

Downloads / month

  2014-05 2014-06 2014-07 total
12. POLYNOMIAL-TIME COMPUTING OVER.pdf 0 0 4 4