论文标题
一种新型的Gröbner基础及其复杂性
A New Type of Gröbner Basis and Its Complexity
论文作者
论文摘要
本文介绍的新类型的理想基础类型构成了基于Buchberger算法和基于WU方法的特征集之间的Gröbner基础之间的妥协。它降低了传统的Gröbner基础的复杂性，并减少了臭名昭著的中间表达膨胀问题和中间系数的膨胀问题。对于新基础的$ s $ polynomial计算最多需要$ o（m \ ln^2m \ ln \ ln m）$ word操作，而$ o（m^6 \ ln^2m）$ Word Operations在Buchberger的Algorithm的Algorithm中是必需的。在这里，$ m $表示在领先系数和其余多项式中的术语数量的上限。新基础用于零维多项式理想，并基于单变量伪分段。但是，与WU在特征集的方法中的伪分类相反，新基础保留了原始理想的代数信息，尤其是解决了理想的成员资格问题。为了确定消除剂的真实因素，我们分析了伪分割的乘数，并开发了比主人零分离器的主要商环的算法。
The new type of ideal basis introduced herein constitutes a compromise between the Gröbner bases based on the Buchberger's algorithm and the characteristic sets based on the Wu's method. It reduces the complexity of the traditional Gröbner bases and subdues the notorious intermediate expression swell problem and intermediate coefficient swell problem to a substantial extent. The computation of an $S$-polynomial for the new bases requires at most $O(m\ln^2m\ln\ln m)$ word operations whereas $O(m^6\ln^2m)$ word operations are requisite in the Buchberger's algorithm. Here $m$ denotes the upper bound for the numbers of terms both in the leading coefficients and for the rest of the polynomials. The new bases are for zero-dimensional polynomial ideals and based on univariate pseudo-divisions. However in contrast to the pseudo-divisions in the Wu's method for the characteristic sets, the new bases retain the algebraic information of the original ideal and in particular, solve the ideal membership problem. In order to determine the authentic factors of the eliminant, we analyze the multipliers of the pseudo-divisions and develop an algorithm over principal quotient rings with zero divisors.
