The Gröbner basis algorithm and subresultant theory

ABSTRACT

We investigate the possibility of constructing for Gro¨bner bases a concept similar to the one provided by subresultants for polynomial remainder sequences. Namely, we try to express the Gro¨bner basis polynomials obtained during the algorithm in terms of matrices having on each row the coefficients of a polynomial from the input basis, shifted by multiplication with a power product.We prove that for the general form of Buchberger's algorithm, the Gro¨bner basis polynomials not only cannot be expressed as determinant polynomials but, in general, they cannot even be obtained by a Gaussian elimination-like process from such matrices.For the Gro¨bner basis polynomials that can be expressed as determinant polynomials we show that we can detect common factors of the coefficients without computing gcd's. For achieving this we generalize Bareiss' matrix triangularization method.

REFERENCES

• Bar68: E.H. Bareiss. Sylvester's Identity and Multistep integer-Preserving Gaussian Elimination. Mathematics of Computation, 22:565-578, 1968.
• BC85: Bruno Buchberger and George E. Collins. Regularity in GrSbner Basis Construction. Talk at the Seminar on Complexity, Oberwolfach, Nov 1985.
• Buc83: Bruno Buchberger. GrSbner Bases, Gaussian Elimination and Euclidean Algorithm. Invited coloquium talk at University of Grenoble, IMAG Institute, 1983.
• Buc85: Bruno Buchberger. GrSbner Bases: An Algorithmic Method in Polynomial Ideal Theory. In N.K. Bose, editor, Multidimensional Systems Theory, pages 184-232. D. Reidel Publishing Company, Dordrecht-Boston-Lancaster, 1985.
• Buc91: Bruno Buchberger. GrSbner Bases and Determinant Polynomials. Invited talk, Workshop on Symbolic Computation in honour of E. Engeler's 60-th birthday, Mar 1991.
• BW93: T. Becket and V. Weispfenning. Gri~bner Bases. Springer Verlag, 1993.
• GPT88: André Galligo , Loic Pottier , Carlo Traverso, Greater Easy Common Divisor and Standard Basis Completion Algorithms, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.162-176, July 04-08, 1988
• Laz83: Daniel Lazard, Gröbner-Bases, Gaussian elimination and resolution of systems of algebraic equations, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.146-156, March 28-30, 1983
• Loo83: Riidiger Loos. Generalized Polynomial Remainder Sequences. In B. Buchberger, G. E. Collins, and R. Loos, editors, Computer Algebra, Symbolic and Algebraic Computation. Springer Verlag, 1983.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials; Computations on matrices

General Terms:
Algorithms, Theory, Verification