TES (Term Elimination Sequence)について

Abstract

In computer algebra, two kinds of polynomial representations are used. One is the recursive representation and another is the monomial representation; see Sect. 1 for details. The resultants were developed on the recursive representation, and the Gröbner bases are computed with the monomial representation. The key operation in Gröbner basis theory is the Spol(G, H) which is defined by canceling the leading-monomials of G and H by multiplying the lowest-order monomials to them re- spectively. Similarly, we can define "TrmElim(G, H)", Elim(G, H) in short, to be an operation which cancels the leading-terms of G and H by multiplying the lowest-order terms to them respectively. Both the Spol(G, H) and the Elim(G, H) are "critical-pair"s of Knuth-Bendix. In this paper, we study the Elim operation for G, H ∈𝕂[x, u], where (u) = (u₁, ..., uₙ), with x>u₁, ..., uₙ. The TES is a degree-decreasing sequence of Elim operations for relatively prime G and H, s.t. degₓ(G) ≥ degₓ(H), i.e., (P₁:=G, P₂:=H, P₃:=Elim(G, H), ..., Pₖ:=Elim(Pₖ-₂, Pₖ-₁)), where Pₖ ∈𝕂[u]. Similarly, we can decrease the x-degree by computing an S-polynomial set, SpS in short. Let Sylv(G, H) denote Sylvester's determinant. We note that most multivariate resultants contain "extraneous factors". We can understand the TES by comparing Sylv(G, H) with resultants by the TES and the SpS. The Sylv(G, H) mostly gives us resultants of large extraneous factors if G and H are sparse. The TES and SpS, with no extraneous-factor removal, will give us resultants with much smaller extraneous factors （⇒ Theorem 2 in 3.3)，but they seldom give us Ŝ₂, the lowest order polynomial in〈{G, H}〉∩𝕂[u]. In order to obtain the Ŝ₂, we must do as follows: suppose we obtained a resultant Pₖ by TES or SpS. Then, we compute Elim(E, Pₖ) or Spol(E, Pₖ) for each element E of TES or SpS. We show a wonderful theory of extraneous-factor removal for TES（⇒ Theorem 3 in 3.3).