mirage

Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials

DSpace/Manakin Repository

 

Search DR-NTU


Advanced Search Subject Search

Browse

My Account

Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials

Show full item record

Title: Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials
Author: Basu, Saugata; Pasechnik, Dmitrii V.; Roy, Marie-Françoise
Copyright year: 2009
Abstract: Let R be a real closed field, , with degY(Q)2, degX(Q)d, , , and with degX(P)d, , . Let SRℓ+k be a semi-algebraic set defined by a Boolean formula without negations, with atoms P=0, P0, P0, . We describe an algorithm for computing the Betti numbers of S generalizing a similar algorithm described in [S. Basu, Computing the top few Betti numbers of semi-algebraic sets defined by quadratic inequalities in polynomial time, Found. Comput. Math. 8 (1) (2008) 45–80]. The complexity of the algorithm is bounded by ((ℓ+1)(s+1)(m+1)(d+1))2O(m+k). The complexity of the algorithm interpolates between the doubly exponential time bounds for the known algorithms in the general case, and the polynomial complexity in case of semi-algebraic sets defined by few quadratic inequalities [S. Basu, Computing the top few Betti numbers of semi-algebraic sets defined by quadratic inequalities in polynomial time, Found. Comput. Math. 8 (1) (2008) 45–80]. Moreover, for fixed m and k this algorithm has polynomial time complexity in the remaining parameters.
Subject: DRNTU::Science::Mathematics::Geometry
Type: Journal Article
Series/ Journal Title: Journal of algebra
School: School of Physical and Mathematical Sciences
Rights: Journal of Algebra @ copyright 2009 Elsevier. The journal's website is located at http://www.elsevier.com/wps/find/journaldescription.cws_home/622850/description.
Version: Accepted version

Files in this item

Files Size Format View
0806.3911v1.pdf 321.0Kb PDF View/Open
   

SFX Query

- Get published version (via NTU subscribed resources)
   

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
Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials 331

Total downloads

All Bitstreams Views
0806.3911v1.pdf 126

Top country downloads

Country Code Views
United States of America 79
Singapore 14
China 8
Russian Federation 7
Japan 4

Top city downloads

city Views
Mountain View 65
Singapore 14
Beijing 4
Porto 2
Southampton 2