dc.contributor.authorBasu, Saugata
dc.contributor.authorPasechnik, Dmitrii V.
dc.contributor.authorRoy, Marie-Françoise
dc.date.accessioned2009-05-08T00:55:09Z
dc.date.available2009-05-08T00:55:09Z
dc.date.copyright2009en_US
dc.date.issued2009
dc.identifier.citationBasu, 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.en_US
dc.identifier.issn0021-8693en_US
dc.identifier.urihttp://hdl.handle.net/10220/4599
dc.description.abstractLet 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.en_US
dc.format.extent24 p.en_US
dc.language.isoenen_US
dc.relation.ispartofseriesJournal of algebraen_US
dc.rightsJournal of Algebra @ copyright 2009 Elsevier. The journal's website is located at http://www.elsevier.com/wps/find/journaldescription.cws_home/622850/description.en_US
dc.subjectDRNTU::Science::Mathematics::Geometry
dc.titleComputing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomialsen_US
dc.typeJournal Article
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen_US
dc.identifier.openurlhttp://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.doihttp://dx.doi.org/10.1016/j.jalgebra.2008.09.043
dc.description.versionAccepted versionen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record