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
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    Gröbner basis
    0 references
    polynomial ideal theory
    0 references
    complexity of algorithm
    0 references
    0 references