Computing minimal polynomials and the degree of unfaithfulness

We show how to compute, based on the Gröbner basis computation, the minimal polynomial of n polynomials in n- 1 variables which contain n- 1 algebraically independent elements. We apply this result to automorphisms of polynomial rings.We also generalize these to rational functions and obtain a criterion for a rational map of an affne space to be birational.     

Resultants and discriminants of Chebyshev and related polynomials

We show that the resultants with respect to of certain linear forms in Chebyshev polynomials with argument are again linear forms in Chebyshev polynomials. Their coefficients and arguments are certain rational functions of the coefficients of the original forms. We apply this to establish several related results involving resultants and discriminants of polynomials, including certain self-reciprocal quadrinomials.

     

On the zeros of certain polynomials

We prove that certain naturally arising polynomials have all of their roots on a vertical line.     

Design of optimal observers with specified eigenvalues via shifted Legendre polynomials

The quadratic performance measure of estimation errors in approximated by using the Legendre polynomial approach for the design of optimal observers with specified distinct and multiple eigenvalues. This method is simple as compared with other design techniques of optimal observers. One example is illustrated, and only a small number (m=6) of shifted Legendre series are needed to produce a much better result than that obtained by the convenient block-pulse function.     

Infinite dimensional generalized Jacobian: Properties and calculus rules

The extension to infinite dimensional domains of Clarke's generalized Jacobian is the focus of this paper. First, a generalization of a Fabian-Preiss theorem to the infinite dimensional setting is obtained. As a consequence, a new formula relating the Clarke's generalized Jacobians corresponding to finite dimensional spaces K, L with K⊆L is established. Furthermore, in the infinite dimensional case, basic properties pertaining the generalized Jacobian are developed and then an identification of this set-valued map is produced. Applications of these results in the form of chain rules including sum and product rules, and a computational formula for continuous selections are derived.     

Analytic Conjugation, Global Attractor, and the Jacobian

It is proved that the dilation \(\lambda f\) of an analytic map \(f\) on \({\bf C}^n$\) with \(f(0)=0,f'(0)=I, |\lambda|>1\) has an analytic conjugation to its linear part \(\lambda x\) if and only if \(f\) is an analytic automorphism on \({\bf C}^n\) and \(x=0\) is a global attractor for the inverse \((\lambda f)^{-1}\). This result is used to show that the dilation of the Jacobian polynomial of [12] is analyticly conjugate to its linear part.     

Ratio asymptotics and weak asymptotic measures for orthogonal polynomials on the real line

We study ratio asymptotics, that is, existence of the limit of P_n+1(z)/P_n(z) (P_n= monic orthogonal polynomial) and the existence of weak limits of p_n² dμ (p_n=P_n/||P_n||) as n→∞ for orthogonal polynomials on the real line. We show existence of ratio asymptotics at a single z₀ with Im(z₀)≠0 implies dμ is in a Nevai class (i.e., a_n→a and b_n→b where a_n,b_n are the off-diagonal and diagonal Jacobi parameters). For μ's with bounded support, we prove p_n² dμ has a weak limit if and only if lim b_n, lim a_2n, and lim a_2n+1 all exist. In both cases, we write down the limits explicitly.     

On the convergence of random polynomials and multilinear forms

We consider different kinds of convergence of homogeneous polynomials and multilinear forms in random variables. We show that for a variety of complex random variables, the almost sure convergence of the polynomial is equivalent to that of the multilinear form, and to the square summability of the coefficients. Also, we present polynomial Khintchine inequalities for complex gaussian and Steinhaus variables. All these results have no analogues in the real case. Moreover, we study the Lp-convergence of random polynomials and derive certain decoupling inequalities without the usual tetrahedral hypothesis. We also consider convergence on “full subspaces” in the sense of Sjögren, both for real and complex random variables, and relate it to domination properties of the polynomial or the multilinear form, establishing a link with the theory of homogeneous polynomials on Banach spaces.     

Approximation of Sobolev classes by polynomials and ridge functions

Let be the usual Sobolev class of functions on the unit ball in , and be the subclass of all radial functions in . We show that for the classes and , the orders of best approximation by polynomials in coincide. We also obtain exact orders of best approximation in of the classes by ridge functions and, as an immediate consequence, we obtain the same orders in for the usual Sobolev classes .     

On the cost of computing roots of polynomials

Recently Smale has obtained probabilistic estimates of the cost of computing a zero of a polynomial using a global version of Newton's method. Roughly speaking, his result says that, with the exception of a set of polynomials where the method fails or is very slow, the cost grows as a polynomial in the degree. He also asked whether similar results hold for PL homotopy methods. This paper gives such a result for a special algorithm of the PL homotopy type devised by Kuhn. Its main result asserts that the cost of computing some zero of a polynomial of degreen to an accuracy of ε (measured by the number of evaluations of the polynomial) grows no faster than O(n ³ log₂(n/ε)). This is a worst case analysis and holds for all polynomials without exception. This work was supported, in part, by National Science Foundation Grant MCS79-10027 and, in part, by a fellowship of the Guggenheim Foundation.     

Computing the minimal covering set

We present the first polynomial-time algorithm for computing the minimal covering set of a (weak) tournament. The algorithm draws upon a linear programming formulation of a subset of the minimal covering set known as the essential set. On the other hand, we show that no efficient algorithm exists for two variants of the minimal covering set–the minimal upward covering set and the minimal downward covering set–unless P equals NP. Finally, we observe a strong relationship between von Neumann–Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other.     

Computing the first eigenvalue of the p-Laplacian via the inverse power method

In this paper, we discuss a new method for computing the first Dirichlet eigenvalue of the p-Laplacian inspired by the inverse power method in finite dimensional linear algebra. The iterative technique is independent of the particular method used in solving the p-Laplacian equation and therefore can be made as efficient as the latter. The method is validated theoretically for any ball in Rn if p>1 and for any bounded domain in the particular case p=2. For p>2 the method is validated numerically for the square.     

Hessian nilpotent polynomials and the Jacobian conjecture

Let and let be the Laplace operator. The main goal of the paper is to show that the well-known Jacobian conjecture without any additional conditions is equivalent to what we call the vanishing conjecture: for any homogeneous polynomial of degree , if for all , then when , or equivalently, when . It is also shown in this paper that the condition () above is equivalent to the condition that is Hessian nilpotent, i.e. the Hessian matrix is nilpotent. The goal is achieved by using the recent breakthrough work of M. de Bondt, A. van den Essen and various results obtained in this paper on Hessian nilpotent polynomials. Some further results on Hessian nilpotent polynomials and the vanishing conjecture above are also derived.

     

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.     

A note on the coefficients of inverse polynomials

We describe some relations on the coefficients of a polynomial in terms of the map that induces and use them to characterize the coefficients of the inverse polynomials of some special classes of permutation polynomials.     

Function-valued Padé-type approximant via the formal orthogonal polynomials and its applications in solving integral equations

A kind of function-valued Padé-type approximant via the formal orthogonal polynomials (FPTAVOP) is introduced on the polynomial space and an algorithm is sketched by means of the formal orthogonal polynomials. This method can be applied to approximate characteristic values and the corresponding characteristic function of Fredholm integral equation of the second kind. Moreover, theoretical analyses show that FPTAVOP method is the most effective one for accelerating the convergence of a sequence of functions. In addition, a typical numerical example is presented to illustrate when the estimates of characteristic value and characteristic function by using this new method are more accurate than other methods.