Given the polynomials f, g ∈ Z[x] of degrees n, m, respectively,
with n > m, three new, and easy to understand methods — along with
the more efficient variants of the last two of them — are presented for the
computation of their subresultant polynomial remainder sequence (prs).
All three methods evaluate a single determinant (subresultant) of an
appropriate sub-matrix of sylvester1, Sylvester’s widely known and used
matrix of 1840 of dimension (m + n) × (m + n), in order to compute the
correct...
In 2000 A. Alesina and M. Galuzzi presented Vincent’s theorem “from a modern point of view” along with two new bisection methods derived from it, B and C. Their profound understanding of Vincent’s theorem is
responsible for simplicity — the characteristic property of these two methods. In this paper we compare the performance of these two new bisection
methods — i.e. the time they take, as well as the number of intervals they examine in order to isolate the real roots of polynomials — against that...
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 this paper we present F LQ, a quadratic complexity bound on the values of the positive roots of polynomials. This bound is an extension of FirstLambda, the corresponding linear complexity bound and, consequently, it is derived from Theorem 3 below. We have implemented FLQ in the Vincent-Akritas-Strzeboński Continued Fractions method (VAS-CF) for the isolation of real roots of polynomials and compared its behavior with that of the theoretically proven best bound, LM Q. Experimental results
indicate...
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)