On computation of the greatest common divisor of several polynomials over a finite field

We propose a probabilistic algorithm to reduce computing the greatest common divisor of m polynomials over a finite field (which requires computing m−1 pairwise greatest common divisors) to computing the greatest common divisor of two polynomials over the same field.     

Pseudo-Strong Regularity Around a Set

A generalization of strong regularity around a vertex subset C of a graph Γ, which makes sense even if Γis non-regular, is studied. Such a structure appears, together with a kind of distance-regularity around C , when an spectral bound concerning the so-called predistance polynomial of C is attained. As a main consequence of these results, it is shown that a regular (connected) graph Γwith d + 1 distinct eigenvalues is distance-regular, and its distance- d graph Γ d is strongly regular with parameters a = c , if and only if the number of vertices at distance d from each vertex satisfies an expression which depends only on the order of Γand the different eigenvalues of Γ.     

正系数多项式倒数逼近的点态和整体估计

利用Ditzian-Totik光滑模对于[0,1]上定义的非角连续函数f(x)，且f(x)≠0，文中证明存在正系数多项式Pn(x)及常数C，使得|f9x)-1/Pn(x)|≤Cωψ^λ（f,n^-1/2(ψ(x) 1/√n)^1-λ)。当λ＝1时，上述结果导出已有的整体估计，而当0≤λ＜1时，得到倒数逼近一个新的点态局部估计。     

On the cost of approximating all roots of a complex polynomial

This work examines the computational complexity of a homotopy algorithm in approximating all roots of a complex polynomialf. It is shown that, probabilistically, monotonic convergence to each of the roots occurs after a determined number of steps. Moreover, in all subsequent steps, each rootz is approximated by a complex numberx, where ifx ₀ =x, x _j =x _j–1 –f(x _j–1)/f(x _j–1),j = 1, 2,, then |x _j –z| < (1/|x ₀ –z|)|x _j–1–z|².     

A fitting algorithm for real coefficient polynomial rooting

A new algorithm for computing all roots of polynomials with real coefficients is introduced. The principle behind the new algorithm is a fitting of the convolution of two subsequences onto a given polynomial coefficient sequence. This concept is used in the initial stage of the algorithm for a recursive slicing of a given polynomial into degree-2 subpolynomials from which initial root estimates are computed in closed form. This concept is further used in a post-fitting stage where the initial root estimates are refined to high numerical accuracy. A reduction of absolute root errors by a factor of 100 compared to the famous Companion matrix eigenvalue method based on the unsymmetric QR algorithm is not uncommon. Detailed computer experiments validate our claims.     

Similar Transposed Sets of Polynomials

This paper studies the effectiveness of another kind of transposed sets of polynomials of one complex variable in closed regions, open discs, at the origin and for all entire functions. In addition, an upper bound for the order of these sets in this case is obtained.     

Solving polynomials by radicals with roots of unity in minimum depth

Let be an algebraic number field. Let be a root of a polynomial which is solvable by radicals. Let be the splitting field of over . Let be a natural number divisible by the discriminant of the maximal abelian subextension of , as well as the exponent of , the Galois group of over . We show that an optimal nested radical with roots of unity for can be effectively constructed from the derived series of the solvable Galois group of over .

     

Certain extremal problems for polynomials

Extensions of two classical results about polynomials, one due to W. Markov and the other due to Duffin and Schaeffer, are obtained in this paper. An interesting result of S. Bernstein, which went unnoticed until it was rediscovered by P. Erdos, years later, is also generalized. Our results are especially amenable to numerical calculations, and may, therefore, be of some practical importance.