Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/101279
Title: | Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials | Authors: | Basu, Saugata Pasechnik, Dmitrii V. Roy, Marie-Françoise |
Keywords: | DRNTU::Science::Mathematics::Geometry | Issue Date: | 2009 | Source: | 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. | Series/Report no.: | Journal of algebra | 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. | URI: | https://hdl.handle.net/10356/101279 http://hdl.handle.net/10220/4599 |
ISSN: | 0021-8693 | DOI: | 10.1016/j.jalgebra.2008.09.043 | Schools: | 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. | Fulltext Permission: | open | Fulltext Availability: | With Fulltext |
Appears in Collections: | SPMS Journal Articles |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
0806.3911v1.pdf | 313.55 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
50
6
Updated on Mar 28, 2024
Web of ScienceTM
Citations
20
6
Updated on Oct 24, 2023
Page view(s) 10
856
Updated on Mar 28, 2024
Download(s) 20
287
Updated on Mar 28, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.