Fast amortized multi-point evaluation

The efficient evaluation of multivariate polynomials at many points is an important operation for polynomial system solving. Kedlaya and Umans have recently devised a theoretically efficient algorithm for this task when the coefficients are integers or when they lie in a finite field. In this paper, we assume that the set of points where we need to evaluate is fixed and “sufficiently generic”. Under these restrictions, we present a quasi-optimal algorithm for multi-point evaluation over general fields. We also present a quasi-optimal algorithm for the opposite interpolation task.     

Quadrature discretization method in tethered satellite control

A pseudospectral method for solving the tethered satellite retrieval problem based on nonclassical orthogonal and weighted interpolating polynomials is presented. Traditional pseudospectral methods expand the state and control trajectories using global Lagrange interpolating polynomials based on a specific class of orthogonal polynomials from the Jacobi family, such as Legendre or Chebyshev polynomials, which are orthogonal with respect to a specific weight function over a fixed interval. Although these methods have many advantages, the location of the collocation points are more or less fixed. The method presented in this paper generalizes the existing methods and allows a much more flexible selection of grid points by the arbitrary selection of the orthogonal weight function and interval. The trajectory optimization problem is converted to set of algebraic equations by discretization of the necessary conditions using a nonclassical pseudospectral method.     

On the Hardy-Littlewood majorant problem for random sets

We study the classical Hardy-Littlewood majorant problem for trigonometric polynomials. We show that the constant in the majorant inequality grows at most like an arbitrary small power of the degree provided the spectrum is chosen at random. We also give an example of a deterministic set where the majorant property fails, i.e., the constant grows like a fixed small power in the degree.     

Critical points and values of complex polynomials

This paper is primarily concerned with complex polynomials which have critical points which are also fixed points. We show that certain perturbations of a critical fixed point satisfy an inequality. This inequality permits us to prove a local version of Smale's mean value conjecture. We also use Thurston's topological characterization of critically finite rational mappings to enumerate explicitly as branched mappings the set of complex polynomials which have all their critical points fixed.     

Multidimensional generalization of the Korous inequality

This paper deals with some qualitative properties of orthogonal polynomials in several variables. The boundedness and relations between two sets of orthonormal polynomials associated with an arbitrary weight function and its extension are investigated. It presents an analogy to Korous' result for general orthogonal polynomials in one variable.     

Algorithm for calculating the roots of polynomials with coefficients in the ring of polynomials over an arbitrary integral domain

A deterministic algorithm for calculating the roots of polynomials in one variable with coefficients in the ring of polynomials in several variables over an arbitrary integral domain is constructed. An estimate for the arithmetic complexity of the algorithm in the worst case is obtained.     

Gale duality bounds for roots of polynomials with nonnegative coefficients

We bound the location of roots of polynomials that have nonnegative coefficients with respect to a fixed but arbitrary basis of the vector space of polynomials of degree at most d. For this, we interpret the basis polynomials as vector fields in the real plane, and at each point in the plane analyze the combinatorics of the Gale dual vector configuration. This approach permits us to incorporate arbitrary linear equations and inequalities among the coefficients in a unified manner to obtain more precise bounds on the location of roots. We apply our technique to bound the location of roots of Ehrhart and chromatic polynomials. Finally, we give an explanation for the clustering seen in plots of roots of random polynomials.     

Multivariate Markov polynomial inequalities and Chebyshev nodes

This article considers the extension of V.A. Markov's theorem for polynomial derivatives to polynomials with unit bound on the closed unit ball of any real normed linear space. We show that this extension is equivalent to an inequality for certain directional derivatives of polynomials in two variables that have unit bound on the Chebyshev nodes. We obtain a sharpening of the Markov inequality for polynomials whose values at specific points have absolute value less than one. We also obtain an interpolation formula for polynomials in two variables where the interpolation points are Chebyshev nodes.     

A local-global principle for linear dependence of noncommutative polynomials

A set of polynomials in noncommuting variables is called locally linearly dependent if their evaluations at tuples of matrices are always linearly dependent. By a theorem of Camino, Helton, Skelton and Ye, a finite locally linearly dependent set of polynomials is linearly dependent. In this short note an alternative proof based on the theory of polynomial identities is given. The method of the proof yields generalizations to directional local linear dependence and evaluations in general algebras over fields of arbitrary characteristic. A main feature of the proof is that it makes it possible to deduce bounds on the size of the matrices where the (directional) local linear dependence needs to be tested in order to establish linear dependence.     

Properties of Algebraic Equations on the Set of E-Functions over the Field of Rational Functions

The paper presents several theorems on the linear and algebraic independence of the values at algebraic points of the set of E-functions related by algebraic equations over the field of rational functions, as well as some estimates of the absolute values of polynomials with integer coefficients in the values of such functions. The results are obtained by using the properties of ideals in the ring of polynomials of several variables formed by equations relating the above functions over the field of rational functions.     

Some researches on multivariate Lagrange interpolation along the sufficiently intersected algebraic manifold

In this article, Lagrange interpolation by polynomials in several variables is studied. Particularly on the sufficiently intersected algebraic manifolds, we discuss the dimension about the interpolation space of polynomials. After defining properly posed set of nodes (or PPSN for short) along the sufficiently intersected algebraic manifolds, we prove the existence of PPSN and give the number of points in PPSN of any degree. Moreover, in order to compute the number of points in PPSN concretely, we propose the operator ? _k with reciprocal difference.     

On the quantitative sharpening of a theorem of birch

The author’s results concerning the null subspaces of arbitrary odd polynomials in several variables are generalized to the case of common null subspaces for several odd polynomials as well as to the complex case.     

Permutable polynomials for several variables

Summary The Russian mathematician P. L. Chebyshev defined and studied a class of polynomials of one variable. These polynomials have many in teresting properties including commutativity and closure with respect to composition. In this article we show how to generalize this property to several variables. Special attention is given to the case of three variables. Results concerning how to compute the polynomials, their value at certain points, closed forms, recurrence relations, and generating functions are presented.     

The expressive power of binary submodular functions

We investigate whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This question has been considered in several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of functions, we answer this question negatively.Our results have several corollaries. First, we characterise precisely which submodular polynomials of arity 4 can be expressed by binary submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities which can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish, for the first time, that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.     

Generation and evaluation of orthogonal polynomials in discrete Sobolev spaces I: algorithms

In this paper, we study theoretically the determination and evaluation of polynomials that are orthogonal with respect to a general discrete Sobolev inner product, that is, an ordinary inner product on the real line plus a finite sum of atomic inner products involving a finite number of derivatives. This Sobolev inner product has the property that the orthogonal polynomials with respect to it satisfy a linear recurrence relation of fixed order. We provide a complete set of formulas to compute the coefficients of this recurrence. Besides, we study the determination of the Fourier–Sobolev coefficients of a finite approximation of a function and the numerical evaluation of the resulting finite series at a general point.     

Existence of solutions for first-order multi-point problems with changing-sign nonlinearity

In this study, conditions for the existence of at least one positive solution to a nonlinear first-order multi-point eigenvalue problem on time scales are discussed. Here the nonlinearity is allowed to take on negative values. The results, which are new for differential/difference equations as well as arbitrary time scales, are based on the Guo–Krasnosel'skii fixed point theorem.     

Geometric relations between the zeros of polynomials

We consider the classical theorem of Grace, which gives a condition for a geometric relation between two arbitrary algebraic polynomials of the same degree. This theorem is one of the basic instruments in the geometry of polynomials. In some applications of the Grace theorem, one of the two polynomials is fixed. In this case, the condition in the Grace theorem may be changed. We explore this opportunity and introduce a new notion of locus of a polynomial. Using the loci of polynomials, we may improve some theorems in the geometry of polynomials. In general, the loci of a polynomial are not easy to describe. We prove some statements concerning the properties of a point set on the extended complex plane that is a locus of a polynomial.     

Stably tame coordinates

In this paper, a class of polynomials in 2 variables is introduced which, in the field case, exactly describes all coordinates in 2 variables. In particular, all of those coordinates are tame. But viewing these polynomials over an arbitrary commutative ring, they are not always coordinates; and when they are, they are usually not tame. But here we will prove, that all of these coordinates are stably tame.     

A note on null subspaces of odd polynomials

Mathematical Notes - We obtain a generalization of the Aron-Hájek theorem about the null subspaces of homogeneous odd polynomials (in several variables) to the case of arbitrary odd polynomials.     

An analogue of the big <Emphasis Type="Italic">q</Emphasis>-Jacobi polynomials in the algebra of symmetric functions

It is well known how to construct a system of symmetric orthogonal polynomials in an arbitrary finite number of variables from an arbitrary system of orthogonal polynomials on the real line. In the special case of the big q-Jacobi polynomials, the number of variables can be made infinite. As a result, in the algebra of symmetric functions, there arises an inhomogeneous basis whose elements are orthogonal with respect to some probability measure. This measure is defined on a certain space of infinite point configurations and hence determines a random point process.