ACM Computing Classification System (1998): F.2.1, G.1.5, I.1.2.
In 1971 using pseudo-divisions - that is, by working in Z[x] -
Brown and Traub computed Euclid’s polynomial remainder sequences (prs’s)
and (proper) subresultant prs’s using sylvester1, the most widely known
form of Sylvester’s matrix, whose determinant defines the resultant of two
polynomials. In this paper we use, for the first time in the literature, the Pell-Gordon
Theorem of 1917, and sylvester2, a little known form...
In 1900 E. B. Van Vleck proposed a very efficient method to compute the Sturm sequence of a polynomial p (x) ∈ Z[x] by triangularizing one of Sylvester’s matrices of p (x) and its derivative p′(x). That method works fine only for the case of complete sequences provided no pivots take place. In 1917, A. J. Pell and R. L. Gordon pointed out this “weakness” in
Van Vleck’s theorem, rectified it but did not extend his method, so that it also works in the cases of: (a) complete Sturm sequences with pivot,...
In 1917 Pell (1) and Gordon used sylvester2, Sylvester’s little
known and hardly ever used matrix of 1853, to compute(2)
the coefficients of a Sturmian remainder — obtained in applying in Q[x],
Sturm’s algorithm on two polynomials f, g ∈ Z[x] of degree n — in terms of
the determinants (3) of the corresponding submatrices of sylvester2.
Thus, they solved a problem that had eluded both J. J. Sylvester, in 1853,
and E. B. Van Vleck, in 1900. (4)
In this paper we extend the work by Pell and Gordon...
Given the polynomials f, g ∈ Z[x] the main result of our paper,
Theorem 1, establishes a direct one-to-one correspondence between the
modified Euclidean and Euclidean polynomial remainder sequences (prs’s) of f, g
computed in Q[x], on one hand, and the subresultant prs of f, g computed
by determinant evaluations in Z[x], on the other.
An important consequence of our theorem is that the signs of Euclidean
and modified Euclidean prs’s - computed either in Q[x] or in Z[x] -
are uniquely determined...
In this paper we present two new methods for computing the
subresultant polynomial remainder sequence (prs) of two polynomials f, g ∈ Z[x].
We are now able to also correctly compute the Euclidean and modified
Euclidean prs of f, g by using either of the functions employed by our
methods to compute the remainder polynomials.
Another innovation is that we are able to obtain subresultant prs’s in
Z[x] by employing the function rem(f, g, x) to compute the remainder
polynomials in [x]. This is achieved...
Download Results (CSV)