Displaying similar documents to “On the Remainders Obtained in Finding the Greatest Common Divisor of Two Polynomials”

On a Theorem by Van Vleck Regarding Sturm Sequences

Akritas, Alkiviadis, Malaschonok, Gennadi, Vigklas, Panagiotis (2013)

Serdica Journal of Computing

Similarity:

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...

Sturm Sequences and Modified Subresultant Polynomial Remainder Sequences

Akritas, Alkiviadis, Malaschonok, Gennadi, Vigklas, Panagiotis (2014)

Serdica Journal of Computing

Similarity:

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...

A Basic Result on the Theory of Subresultants

Akritas, Alkiviadis G., Malaschonok, Gennadi I., Vigklas, Panagiotis S. (2016)

Serdica Journal of Computing

Similarity:

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...

Subresultant Polynomial Remainder Sequences Obtained by Polynomial Divisions in Q[x] or in Z[x]

Akritas, Alkiviadis G., Malaschonok, Gennadi I., Vigklas, Panagiotis S. (2016)

Serdica Journal of Computing

Similarity:

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...

Comparison of algorithms for calculation of the greatest common divisor of several polynomials

Eckstein, Jiří, Zítko, Jan

Similarity:

The computation of the greatest common divisor (GCD) has many applications in several disciplines including computer graphics, image deblurring problem or computing multiple roots of inexact polynomials. In this paper, Sylvester and Bézout matrices are considered for this purpose. The computation is divided into three stages. A rank revealing method is shortly mentioned in the first one and then the algorithms for calculation of an approximation of GCD are formulated. In the final stage...

Structured Matrix Methods Computing the Greatest Common Divisor of Polynomials

Dimitrios Christou, Marilena Mitrouli, Dimitrios Triantafyllou (2017)

Special Matrices

Similarity:

This paper revisits the Bézout, Sylvester, and power-basis matrix representations of the greatest common divisor (GCD) of sets of several polynomials. Furthermore, the present work introduces the application of the QR decomposition with column pivoting to a Bézout matrix achieving the computation of the degree and the coeffcients of the GCD through the range of the Bézout matrix. A comparison in terms of computational complexity and numerical effciency of the Bézout-QR, Sylvester-QR,...

A fixed point method to compute solvents of matrix polynomials

Fernando Marcos, Edgar Pereira (2010)

Mathematica Bohemica

Similarity:

Matrix polynomials play an important role in the theory of matrix differential equations. We develop a fixed point method to compute solutions of matrix polynomials equations, where the matricial elements of the matrix polynomial are considered separately as complex polynomials. Numerical examples illustrate the method presented.

Matrix quadratic equations column/row reduced factorizations and an inertia theorem for matrix polynomials

Irina Karelin, Leonid Lerer (2001)

International Journal of Applied Mathematics and Computer Science

Similarity:

It is shown that a certain Bezout operator provides a bijective correspondence between the solutions of the matrix quadratic equation and factorizatons of a certain matrix polynomial (which is a specification of a Popov-type function) into a product of row and column reduced polynomials. Special attention is paid to the symmetric case, i.e. to the Algebraic Riccati Equation. In particular, it is shown that extremal solutions of such equations correspond to spectral factorizations of...

A subresultant theory of multivariate polynomials.

Laureano González Vega (1990)

Extracta Mathematicae

Similarity:

In Computer Algebra, Subresultant Theory provides a powerful method to construct algorithms solving problems for polynomials in one variable in an optimal way. So, using this method we can compute the greatest common divisor of two polynomials in one variable with integer coefficients avoiding the exponential growth of the coefficients that will appear if we use the Euclidean Algorithm. In this note, generalizing a forgotten construction appearing in [Hab], we extend the...

On a decomposition of polynomials in several variables

Andrzej Schinzel (2002)

Journal de théorie des nombres de Bordeaux

Similarity:

One considers representation of a polynomial in several variables as the sum of values of univariate polynomials taken at linear combinations of the variables.

On stable polynomials

Miloslav Nekvinda (1989)

Aplikace matematiky

Similarity:

The article is a survey on problem of the theorem of Hurwitz. The starting point of explanations is Schur's decomposition theorem for polynomials. It is showed how to obtain the well-known criteria on the distribution of roots of polynomials. The theorem on uniqueness of constants in Schur's decomposition seems to be new.

Factorization makes fast Walsh, PONS and other Hadamard-like transforms easy

Kautsky, Jaroslav

Similarity:

A simple device, based on the factorization of invertible matrix polynomials, enabling to identify the possibility of fast implementation of linear transforms is presented. Its applicability is demonstrated in the case of Hadamard matrices and their generalization, Hadamard matrix polynomials.