Gröbner bases

From Algorithm Wiki
Revision as of 10:56, 10 October 2022 by Admin (talk | contribs) (Created page with "== Problem Description== In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring K[x1, ..,xn] over a field K. == Bounds Chart == 1050px == Step Chart == 1050px == Improvement Table == {| class="wikitable" style="text-align:center;...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Problem Description

In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring K[x1, ..,xn] over a field K.

Bounds Chart

Gröbner basesBoundsChart.png

Step Chart

Gröbner basesStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial Buchberger's algorithm (1976)
Polynomial > 3 Faugère F4 algorithm (1999)

Faugère F5 algorithm (2002)

Cubic
Quadratic
nlogn
Linear
logn