|
|
|
|
|
Let the normal form of a polynomial p modulo a polynomial ideal with respect to a term order be defined as the polynomial that is within the polynomial ideal coset of p minimal with respect to the given term order.
The main result of this thesis is the following. In a multivariate polynomial ring over the field of rational numbers, let a polynomial p be given. Further, a collection of polynomials that generate a polynomial ideal, and a collection of integers that specify, according to certain rules, a term order on the polynomial ring are given. There is an algorithm that computes the normal form of p modulo the polynomial ideal generated by the given collection of polynomials with respect to the term order specified by the given collection of integers. The amount of work space used by this algorithm, regarded as a function of the amount of space necessary for writing down the input, is bounded by an exponentially growing function.
An exponential and, hence, asymptotically corresponding lower bound on the space needed by every algorithm computing normal forms of polynomials is well established. This implies that the presented algorithm is asymptotically optimal with respect to its space requirement.
The principal application of this normal form algorithm is the computation of Gröbner-bases using space that grows exponentially with the input size. As in the case of the normal form algorithm, this space requirement asymptotically matches a corresponding lower bound and is, therefore, optimal. Further applications are in ideal theoretic problems arising in algebraic geometry.