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 simple item record

dc.contributor.author Basu, Saugata
dc.contributor.author Pasechnik, Dmitrii V.
dc.contributor.author Roy, Marie-Françoise
dc.date.accessioned 2009-05-08T00:55:09Z
dc.date.available 2009-05-08T00:55:09Z
dc.date.copyright 2009
dc.date.issued 2009-05-08T00:55:09Z
dc.identifier.citation Basu, S., Pasechnik, D. V., & Roy, M.-F. (2009). Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials. Journal of algebra, 21(8), 2206-2229.
dc.identifier.issn 0021-8693
dc.identifier.uri http://hdl.handle.net/10220/4599
dc.description.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.
dc.format.extent 24 p.
dc.language.iso en
dc.relation.ispartofseries Journal of algebra
dc.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.
dc.subject DRNTU::Science::Mathematics::Geometry
dc.title Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials
dc.type Journal Article
dc.contributor.school School of Physical and Mathematical Sciences
dc.identifier.openurl http://sfxna09.hosted.exlibrisgroup.com:3410/ntu/sfxlcl3?sid=metalib:ELSEVIER_SCOPUS&id=doi:&genre=&isbn=&issn=&date=2009&volume=321&issue=8&spage=2206&epage=2229&aulast=Basu&aufirst=%20S&auinit=&title=Journal%20of%20Algebra&atitle=Computing%20the%20Betti%20numbers%20of%20semi%2Dalgebraic%20sets%20defined%20by%20partly%20quadratic%20systems%20of%20polynomials
dc.identifier.doi http://dx.doi.org/10.1016/j.jalgebra.2008.09.043
dc.description.version Accepted version

Files in this item

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

This item appears in the following Collection(s)

Show simple item record

Statistics

Total views

All Items Views
Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials 325

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

Downloads / month

  2014-09 2014-10 2014-11 total
0806.3911v1.pdf 0 0 5 5