Loading...
Please wait, while we are loading the content...
Similar Documents
Degree Bounds and Complexity of Gröbner Bases of Important Classes of Polynomial Ideals
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ritscher, Stephan |
| Copyright Year | 2012 |
| Abstract | The method of Buchberger allows to effectively solve the membership problem in polynomial ideals and many other interesting problems. Mayr and Meyer showed that this is very expensive in the worst case. So the problem has to be specialized for more efficient computations. As previous results show, the complexity of the membership problem is mainly related to the degrees of the representation problem and Grobner bases which are studied in the first part of the thesis. The main contributions are upper and lower bounds for Grobner bases depending on the ideal dimension and some results for toric ideals. In the second part, these findings are applied to questions of complexity. The presentation comprises an incremental space-efficient algorithm for the computation of Grobner bases, an algorithm in polylogarithmic space for the membership problem in toric ideals and the space-efficient computation of the radicals of low-dimensional ideals. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://mediatum.ub.tum.de/doc/1006213/1006213.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
