Content deleted Content added
Salix alba (talk | contribs) →Algorithm: fix capitalisation of indices in formula |
Citation bot (talk | contribs) Alter: pages. Add: s2cid. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 70/530 |
||
Line 25:
== Complexity ==
The [[time complexity|computational complexity]] of Buchberger's algorithm is very difficult to estimate, because of the number of choices that may dramatically change the computation time. Nevertheless, T. W. Dubé has proved<ref>{{cite journal|doi=10.1137/0219053|title=The Structure of Polynomial Ideals and Gröbner Bases|journal=SIAM Journal on Computing|volume=19|issue=4|pages=
:<math>2\left(\frac{d^2}{2} +d\right)^{2^{n-2}}</math>,
where {{math|''n''}} is the number of variables, and {{math|''d''}} the maximal [[total degree]] of the input polynomials. This allows, in theory, to use [[linear algebra]] over the [[vector space]] of the polynomials of degree bounded by this value, for getting an algorithm of complexity
Line 57:
| doi = 10.1145/1088216.1088219
| mr = 0463136
| s2cid = 15179417
}} <!-- Note: This citation data is from ACM; the citation at MathWorld has several errors. -->
* David Cox, John Little, and Donald O'Shea (1997). ''Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra'', Springer. {{ISBN|0-387-94680-2}}.
* Vladimir P. Gerdt, Yuri A. Blinkov (1998). ''Involutive Bases of Polynomial Ideals'', Mathematics and Computers in Simulation, 45:519ff
| |||