On factoring parametric multivariate polynomials

This paper presents a new algorithm for the absolute factorization of parametric multivariate polynomials over the field of rational numbers. This algorithm decomposes the parameters space into a finite number of constructible sets. The absolutely irreducible factors of the input parametric polynomial are given uniformly in each constructible set. The algorithm is based on a parametric version of Hensel's lemma and an algorithm for quantifier elimination in the theory of algebraically closed field in order to reduce the problem of finding absolute irreducible factors to that of representing solutions of zero-dimensional parametric polynomial systems. The complexity of this algorithm is single exponential in the number n of the variables of the input polynomial, its degree d w.r.t. these variables and the number r of the parameters.     

Reliable determination of interpolating polynomials

This paper addresses a fundamental problem in mathematics and numerical analysis, that of determining a polynomial interpolant to specified data. The data is taken as consisting of a set of points (abscissae), at each of which is specified a function value. Additionally, at each point, any number of leading derivative values of the function may be given. Mathematically, this problem is solved. The classical Lagrangian interpolation formula applies in the derivative-free case, and the Newton form of the interpolating polynomial in general.Numerically, few reliable algorithms are available; most published algorithms concentrate on speed of computation. This paper describes an algorithm that delivers the required polynomial in Chebyshev form. It is based on the repeated use of the Newton representation, with a data ordering strategy and iterative refinement to improve accuracy, using a carefully devised merit function to measure success. The algorithm attempts to provide a polynomial that is stable in the sense of backward error analysis, i.e. that is exact for slightly perturbed data.Implementations of the algorithm have been in use since the early 1980s in the NAG Library and NPL's Data Approximation Subroutine Library (DASL). In addition to providing polynomial interpolants in their own right, these implementations are used as computational modules in the NAG and DASL routines for constrained least-squares polynomial data fitting.This paper constitutes the first detailed presentation of the algorithm.     

An efficient algorithm for factoring polynomials over algebraic extension field

An efficient algorithm is proposed for factoring polynomials over an algebraic extension field defined by a polynomial ring modulo a maximal ideal. If the maximal ideal is given by its Gröbner basis, no extra Gröbner basis computation is needed for factoring a polynomial over this extension field. Nothing more than linear algebraic technique is used to get a characteristic polynomial of a generic linear map. Then this polynomial is factorized over the ground field. From its factors, the factorization of the polynomial over the extension field is obtained. The algorithm has been implemented in Magma and computer experiments indicate that it is very efficient, particularly for complicated examples.     

Representations of orthogonal polynomials

Zeilberger's algorithm provides a method to compute recurrence and differential equations from given hypergeometric series representations, and an adaption of Almquist and Zeilberger computers recurrence and differential equations for hyperexponential integrals. Further versions of this algorithm allow the computation of recurrence and differential equations from Rodrigues type formulas and from generating functions. In particular, these algorithms can be used to compute the differential/difference and recurrence equations for the classical continuous and discrete orthogonal polynomials from their hypergeometric representations, and from their Rodrigues representations and generating functions.In recent work, we used an explicit formula for the recurrence equation of families of classical continuous and discrete orthogonal polynomials, in terms of the coefficients of their differential/difference equations, to give an algorithm to identify the polynomial system from a given recurrence equation.In this article we extend these results by presenting a collection of algorithms with which any of the conversions between the differential/difference equation, the hypergeometric representation, and the recurrence equation is possible.The main technique is again to use explicit formulas for structural identities of the given polynomial systems.     

On the reconstruction of polynomial automorphisms from their face polynomials

A generalization of the resultant inversion formulae of McKay and Wang for polynomial automorphisms to higher dimensions is given. Furthermore an algorithm, using Gröbner bases, is described to reconstruct polynomial automorphisms from their face polynomials.     

Polynomial evaluation and associated polynomials

We show a connection between the Clenshaw algorithm for evaluating a polynomial , expanded in terms of a system of orthogonal polynomials, and special linear combinations of associated polynomials. These results enable us to get the derivatives of analogously to the Horner algorithm for evaluating polynomials in monomial representations. Furthermore we show how a polynomial given in monomial (!) representation can be evaluated for using the Clenshaw algorithm without complex arithmetic. From this we get a connection between zeros of polynomials expanded in terms of Chebyshev polynomials and the corresponding polynomials in monomial representation with the same coefficients. Received January 2, 1995 / Revised version received April 9, 1997     

多项式分裂可行问题

本文研究多项式分裂可行问题,即由多项式不等式定义的分裂可行问题,包括凸与非凸、可行与不可行的问题;给出多项式分裂可行问题解集的半定松弛表示;研究其半定松弛化问题的性质;并基于这些性质建立求解多项式分裂可行问题的半定松弛算法.本文在较为一般的条件下证明了,如果分裂可行问题有解,则可通过本文建立的算法求得一个解点;如果问题无解,则该算法能够判别问题不可行.最后通过数值实验对算法进行验证.     

On sequences of Hurwitz polynomials related to orthogonal polynomials

ABSTRACT

In this contribution, we explore the well-known connection between Hurwitz and orthogonal polynomials. Namely, given a Hurwitz polynomial, it is shown that it can be decomposed into two parts: a polynomial that is orthogonal with respect to some positive measure supported in the positive real axis and its corresponding second-kind polynomial. Conversely, given a sequence of orthogonal polynomials with respect to a positive measure supported in the positive real axis, a sequence of Hurwitz polynomials can be constructed. Based on that connection, we construct sequences of Hurwitz polynomials that satisfy a recurrence relation, in a similar way as the orthogonal polynomials do. Even more, we present a way to construct families of Hurwitz polynomials using two sequences of parameters and a recurrence relation that constitutes an analogue of Favard's theorem in the theory of orthogonal polynomials.     

Computing roots of polynomials on vector processing machines

The Durand and Kerner algorithm for the computation of roots of polynomials has not been og reat use up to now. The reason is the existence of more efficient methods for computers ofthe SISD type (sequential). Actually vector processing machines such as CRAY-1 or CDC CYBER 205 must bring Durand's algorithm back to honour because of its possibility of extensive vectorization. However, as the method has its maximum efficiency for a polynomial with no multiple root a criterion using Vignes' permutation-perturbation method is given to know whether the roots are all distinct or not. The optimum criterion for stopping the iterations is shown to be vectorizable and some useful properties of the method are given. Numerical examples are considered.     

Band-limited signal extrapolation by truncated Bernstein polynomials

An algorithm is given for everywhere extrapolating a band-limited signal known only on an interval of arbitrary finite length. The scheme utilizes a finite number of equally spaced samples of the given function and provides a time-limited polynomial approximation. The approximation functions are shown to converge everywhere pointwise and uniformly in any compact interval to the band-limited signal. When the original band-limited signal is also Lebesgue integrable it is also established that the Fourier transform of the approximating signal converges uniformly to the Fourier transform of the original signal.     

Detecting hyperbolic and definite matrix polynomials

Hyperbolic or more generally definite matrix polynomials are important classes of Hermitian matrix polynomials. They allow for a definite linearization and can therefore be solved by a standard algorithm for Hermitian matrices. They have only real eigenvalues which can be characterized as minmax and maxmin values of Rayleigh functionals, but there is no easy way to test if a given polynomial is hyperbolic or definite or not. Taking advantage of the safeguarded iteration which converges globally and monotonically to extreme eigenvalues we obtain an efficient algorithm that identifies hyperbolic or definite polynomials and enables the transformation to an equivalent definite linear pencil. Numerical examples demonstrate the efficiency of the approach.     

Testing low‐degree polynomials over prime fields

We present an efficient randomized algorithm to test if a given function f : ?? → ??_p (where p is a prime) is a low‐degree polynomial. This gives a local test for Generalized Reed‐Muller codes over prime fields. For a given integer t and a given real ε > 0, the algorithm queries f at O( ) points to determine whether f can be described by a polynomial of degree at most t. If f is indeed a polynomial of degree at most t, our algorithm always accepts, and if f has a relative distance at least ε from every degree t polynomial, then our algorithm rejects f with probability at least . Our result is almost optimal since any such algorithm must query f on at least points. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Relative node polynomials for plane curves

We generalize the recent work of S.?Fomin and G.?Mikhalkin on polynomial formulas for Severi degrees. The degree of the Severi variety of plane curves of degree d and ?? nodes is given by a polynomial in d, provided ?? is fixed and d is large enough. We extend this result to generalized Severi varieties parametrizing plane curves that, in addition, satisfy tangency conditions of given orders with respect to a given line. We show that the degrees of these varieties, appropriately rescaled, are given by a combinatorially defined ??relative node polynomial?? in the tangency orders, provided the latter are large enough. We describe a method to compute these polynomials for arbitrary ??, and use it to present explicit formulas for ????6. We also give a threshold for polynomiality, and compute the first few leading terms for any???.     

The stable computation of formal orthogonal polynomials

For many applications — such as the look-ahead variants of the Lanczos algorithm — a sequence of formal (block-)orthogonal polynomials is required. Usually, one generates such a sequence by taking suitable polynomial combinations of a pair of basis polynomials. These basis polynomials are determined by a look-ahead generalization of the classical three term recurrence, where the polynomial coefficients are obtained by solving a small system of linear equations. In finite precision arithmetic, the numerical orthogonality of the polynomials depends on a good choice of the size of the small systems; this size is usually controlled by a heuristic argument such as the condition number of the small matrix of coefficients. However, quite often it happens that orthogonality gets lost.We present a new variant of the Cabay-Meleshko algorithm for numerically computing pairs of basis polynomials, where the numerical orthogonality is explicitly monitored with the help of stability parameters. A corresponding error analysis is given. Our stability parameter is shown to reflect the condition number of the underlying Hankel matrix of moments. This enables us to prove the weak and strong stability of our method, provided that the corresponding Hankel matrix is well-conditioned.This work was partially supported by the HCM project ROLLS, under contract CHRX-CT93-0416.     

On coefficients of polynomials over finite fields

In this paper we study the relation between coefficients of a polynomial over finite field Fq and the moved elements by the mapping that induces the polynomial. The relation is established by a special system of linear equations. Using this relation we give the lower bound on the number of nonzero coefficients of polynomial that depends on the number m of moved elements. Moreover we show that there exist permutation polynomials of special form that achieve this bound when m|q−1. In the other direction, we show that if the number of moved elements is small then there is an recurrence relation among these coefficients. Using these recurrence relations, we improve the lower bound of nonzero coefficients when m?q−1 and . As a byproduct, we show that the moved elements must satisfy certain polynomial equations if the mapping induces a polynomial such that there are only two nonzero coefficients out of 2m consecutive coefficients. Finally we provide an algorithm to compute the coefficients of the polynomial induced by a given mapping with O(q3/2) operations.     

The Green polynomials via vertex operators

An iterative formula for the Green polynomial is given using the vertex operator realization of the Hall-Littlewood function. Based on this, (1) a general combinatorial formula of the Green polynomial is given; (2) several compact formulas are given for Green's polynomials associated with upper partitions of length ≤3 and the diagonal lengths ≤3; (3) a Murnaghan-Nakayama type formula for the Green polynomial is obtained; and (4) an iterative formula is derived for the bitrace of the finite general linear group G and the Iwahori-Hecke algebra of type A on the permutation module of G by its Borel subgroup.     

Algorithms for finding the minimal polynomials and inverses of resultant matrices

In this paper, algorithms for computing the minimal polynomial and the common minimal polynomial of resultant matrices over any field are presented by means of the approach for the Gröbner basis of the ideal in the polynomial ring, respectively, and two algorithms for finding the inverses of such matrices are also presented. Finally, an algorithm for the inverse of partitioned matrix with resultant blocks over any field is given, which can be realized by CoCoA 4.0, an algebraic system over the field of rational numbers or the field of residue classes of modulo prime number. We get examples showing the effectiveness of the algorithms.     

Harmonic polynomials and the divisibility problem

An easy way to construct a fist harmonic polynomial component of any polynomial is given.

     

On best-approximation polynomials in the Hausdorff metric

A definition of the Hausdorff alternance is given. In its terms we give a sufficient condition for an algebraic polynomial to have minimal deviation from a function f in the Hausdorff α-metric. A condition under which a polynomial P_n is the unique best-approximation polynomial for a function f and a necessary condition for P_n to have minimal deviation from f are given. Similar theorems for 2π-periodic functions are formulated. Bibliography: 3 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 217, 1994, pp. 130–143.     

A discrete logarithm-based approach to compute low-weight multiples of binary polynomials

Being able to compute efficiently a low-weight multiple of a given binary polynomial is often a key ingredient of correlation attacks to LFSR-based stream ciphers. The best known general purpose algorithm is based on the generalized birthday problem. We describe an alternative approach which is based on discrete logarithms and can take advantage of the structure of the polynomial. In some cases it has much lower memory complexity requirements with a comparable time complexity.