A New Type of Bases for Zero-dimensional Ideals
share
We formulate a substantial improvement on Buchberger's algorithm for Gröbner bases of zero-dimensional ideals. The improvement scales down the phenomenon of intermediate expression swell as well as the complexity of Buchberger's algorithm to a significant degree. The idea is to compute a new type of bases over principal ideal rings instead of over fields like Gröbner bases. The generalizations of Buchberger's algorithm from over fields to over rings are abundant in the literature. However they are limited to either computations of strong Gröbner bases or modular computations of the numeral coefficients of ideal bases with no essential improvement on the algorithmic complexity. In this paper we make pseudo-divisions with multipliers to enhance computational efficiency. In particular, we develop a new methodology in determining the authenticity of the factors of the pseudo-eliminant, i.e., we compare the factors with the multipliers of the pseudo-divisions instead of the leading coefficients of the basis elements. In order to find out the exact form of the eliminant, we contrive a modular algorithm of proper divisions over principal quotient rings with zero divisors. The pseudo-eliminant and proper eliminants and their corresponding bases constitute a decomposition of the original ideal. In order to address the ideal membership problem, we elaborate on various characterizations of the new type of bases. In the complexity analysis we devise a scenario linking the rampant intermediate coefficient swell to Bézout coefficients, partially unveiling the mystery of hight-level complexity associated with the computation of Gröbner bases. Finally we make exemplary computations to demonstrate the conspicuous difference between Gröbner bases and the new type of bases.
READ FULL TEXT
