Content deleted Content added
m Replace magic links with templates per local RfC and MediaWiki RfC |
m Typo fixing, replaced: Simluation → Simulation |
||
Line 27:
On the other hand, there are examples<ref>{{cite journal|doi=10.1016/0001-8708(82)90048-2|title=The complexity of the word problems for commutative semigroups and polynomial ideals|journal=Advances in Mathematics|volume=46|issue=3|pages=305|year=1982|last1=Mayr|first1=Ernst W|last2=Meyer|first2=Albert R}}</ref> where the Gröbner basis contains elements of degree
:<math>d^{2^{\Omega(n)}}</math>,
and above upper bound of complexity is almost optimal, up to a constant factor in the second exponent
Since its discovery, many variants of Buchberger's have been introduced to improve its efficiency. [[Faugère's F4 and F5 algorithms]] are presently the most efficient algorithms for computing Gröbner bases, and allow to compute routinely Gröbner bases consisting of several hundreds of polynomials, having each several hundreds of terms and coefficients of several hundreds of digits.
Line 54:
}} <!-- 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
== External links ==
| |||