The Hilbert zonotope and a polynomial time algorithm for universal Gröbner bases. (Q1408266)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Hilbert zonotope and a polynomial time algorithm for universal Gröbner bases. |
scientific article |
Statements
The Hilbert zonotope and a polynomial time algorithm for universal Gröbner bases. (English)
0 references
15 September 2003
0 references
The computation of a Gröbner basis is one of the fundamental algorithmic processes in polynomial ideal theory. Unfortunately, this process depends exponentially on the number of variables. Considering a fixed number \(d\) of variables, the authors show that a universal Gröbner basis for an ideal \(I\) in the multivariate polynomial ring \(F[x]\) can be computed in time depending polynomially on \(n\), the \(F\)-dimension of \(F[x]/I\). Of course, \(d\) enters exponentially in the complexity bound, which could be stated a bit more prominently in the title and abstract.
0 references
Gröbner basis
0 references
polynomial ideal theory
0 references
complexity of algorithm
0 references
0 references
0 references