Solving polynomial least squares problems via semidefinite programming relaxations

A polynomial optimization problem whose objective function is represented as a sum of positive and even powers of polynomials, called a polynomial least squares problem, is considered. Methods to transform a polynomial least square problem to polynomial semidefinite programs to reduce degrees of the polynomials are discussed. Computational efficiency of solving the original polynomial least squares problem and the transformed polynomial semidefinite programs is compared. Numerical results on selected polynomial least square problems show better computational performance of a transformed polynomial semidefinite program, especially when degrees of the polynomials are larger.     

On the refinement of Cauchy's theorem and Pellet's theorem

Using the relationship of a polynomial and its associated polynomial, we derived a necessary and sufficient condition for determining all roots of a given polynomial on the circumference of a circle defined by its associated polynomial. By employing the technology of analytic inequality and the theory of distribution of zeros of meromorphic function, we refine two classical results of Cauchy and Pellet about bounds of modules of polynomial zeros. Sufficient conditions are obtained for the polynomial whose Cauchy's bound and Pellet's bounds are strict bounds. The characteristics is given for the polynomial whose Cauchy's bound or Pellet's bounds can be achieved by the modules of zeros of the polynomial.     

Two dimensional coordinate polynomials and dominant maps

A polynomial in n variables is called a coordinate polynomial if it is a component of a polynomial automorphism of n-space. For n=2 and a ground field of characteristic zero, we show that a polynomial is a coordinate polynomial if its composition with a dominant endomorphism of 2-space is a coordinate polynomial.     

On polynomial reciprocity law

The well-known law of quadratic reciprocity has over 150 proofs in print. We establish a relation between polynomial Jacobi symbols and resultants of polynomials over finite fields. Using this relation, we prove the polynomial reciprocity law and obtain a polynomial analogue of classical Burde's quartic reciprocity law. Under the use of our polynomial Poisson summation formula and the evaluation of polynomial exponential map, we get a reciprocity for the generalized polynomial quadratic Gauss sums.     

To Solving Multiparameter Problems of Algebra. I. Methods for Computing Complete Polynomials and Their Applications

The notion of a complete polynomial of a multiparameter polynomial matrix, generalizing that of an invariant polynomial of a one-parameter polynomial matrix, is introduced. Methods for computing complete polynomials are suggested. Applications of these methods to various spectral problems for polynomial matrices are considered. Bibliography: 7 titles.     

The interlace polynomial of a graph

Motivated by circle graphs, and the enumeration of Euler circuits, we define a one-variable “interlace polynomial” for any graph. The polynomial satisfies a beautiful and unexpected reduction relation, quite different from the cut and fuse reduction characterizing the Tutte polynomial.It emerges that the interlace graph polynomial may be viewed as a special case of the Martin polynomial of an isotropic system, which underlies its connections with the circuit partition polynomial and the Kauffman brackets of a link diagram. The graph polynomial, in addition to being perhaps more broadly accessible than the Martin polynomial for isotropic systems, also has a two-variable generalization that is unknown for the Martin polynomial. We consider extremal properties of the interlace polynomial, its values for various special graphs, and evaluations which relate to basic graph properties such as the component and independence numbers.     

The Las Vergnas polynomial for embedded graphs

The Las Vergnas polynomial is an extension of the Tutte polynomial to cellularly embedded graphs. It was introduced by Michel Las Vergnas in 1978 as special case of his Tutte polynomial of a morphism of matroids. While the general Tutte polynomial of a morphism of matroids has a complete set of deletion–contraction relations, its specialisation to cellularly embedded graphs does not. Here we extend the Las Vergnas polynomial to graphs in pseudo-surfaces. We show that in this setting we can define deletion and contraction for embedded graphs consistently with the deletion and contraction of the underlying matroid perspective, thus yielding a version of the Las Vergnas polynomial with complete recursive definition. This also enables us to obtain a deeper understanding of the relationships among the Las Vergnas polynomial, the Bollobás–Riordan polynomial, and the Krushkal polynomial. We also take this opportunity to extend some of Las Vergnas’ results on Eulerian circuits from graphs in surfaces of low genus to graphs in surfaces of arbitrary genus.     

The characteristic polynomial of a multiarrangement

Given a multiarrangement of hyperplanes we define a series by sums of the Hilbert series of the derivation modules of the multiarrangement. This series turns out to be a polynomial. Using this polynomial we define the characteristic polynomial of a multiarrangement which generalizes the characteristic polynomial of an arrangement. The characteristic polynomial of an arrangement is a combinatorial invariant, but this generalized characteristic polynomial is not. However, when the multiarrangement is free, we are able to prove the factorization theorem for the characteristic polynomial. The main result is a formula that relates ‘global’ data to ‘local’ data of a multiarrangement given by the coefficients of the respective characteristic polynomials. This result gives a new necessary condition for a multiarrangement to be free. Consequently it provides a simple method to show that a given multiarrangement is not free.     

Polynomial Reproduction in Subdivision

We study conditions on the matrix mask of a vector subdivision scheme ensuring that certain polynomial input vectors yield polynomial output again. The conditions are in terms of a recurrence formula for the vectors which determine the structure of polynomial input with this property. From this recurrence, we obtain an algorithm to determine polynomial input of maximal degree. The algorithm can be used in the design of masks to achieve a high order of polynomial reproduction.     

A Tutte polynomial for maps II: The non-orientable case

We construct a new polynomial invariant of maps (graphs embedded in a closed surface, orientable or non-orientable), which contains as specializations the Krushkal polynomial, the Bollobás—Riordan polynomial, the Las Vergnas polynomial, and their extensions to non-orientable surfaces, and hence in particular the Tutte polynomial. Other evaluations include the number of local flows and local tensions taking non-identity values in a given finite group.     

The Differential Counting Polynomial

The aim of this paper is a quantitative analysis of the solution set of a system of polynomial nonlinear differential equations, both in the ordinary and partial case. Therefore, we introduce the differential counting polynomial, a common generalization of the dimension polynomial and the (algebraic) counting polynomial. Under mild additional assumptions, the differential counting polynomial decides whether a given set of solutions of a system of differential equations is the complete set of solutions.     

A note on the complexity of a phaseless polynomial interpolation

In this paper we revisit the classical problem of polynomial interpolation, with a slight twist; namely, polynomial evaluations are available up to a group action of the unit circle on the complex plane. It turns out that this new setting allows for a phaseless recovery of a polynomial in a polynomial time.     

Congruence-preserving functions on Stone and Kleene algebras

We investigate local polynomial functions on Stone algebras and on Kleene algebras. We find a generating set for the clone of all local polynomial functions. We also represent local polynomial functions on a given algebra by polynomial functions of some canonical extension of this algebra.     

Multivariate Polynomial Minimization and Its Application in Signal Processing

We make a conjecture that the number of isolated local minimum points of a 2n-degree or (2n+1)-degree r-variable polynomial is not greater than n ^r when n 2. We show that this conjecture is the minimal estimate, and is true in several cases. In particular, we show that a cubic polynomial of r variables may have at most one local minimum point though it may have 2^r critical points. We then study the global minimization problem of an even-degree multivariate polynomial whose leading order coefficient tensor is positive definite. We call such a multivariate polynomial a normal multivariate polynomial. By giving a one-variable polynomial majored below a normal multivariate polynomial, we show the existence of a global minimum of a normal multivariate polynomial, and give an upper bound of the norm of the global minimum and a lower bound of the global minimization value. We show that the quartic multivariate polynomial arising from broad-band antenna array signal processing, is a normal polynomial, and give a computable upper bound of the norm of the global minimum and a computable lower bound of the global minimization value of this normal quartic multivariate polynomial. We give some sufficient and necessary conditions for an even order tensor to be positive definite. Several challenging questions remain open.     

Polynomial numerical hulls of matrix polynomials,II

In this article, we study some algebraic and geometrical properties of polynomial numerical hulls of matrix polynomials and joint polynomial numerical hulls of a finite family of matrices (possibly the coefficients of a matrix polynomial). Also, we study polynomial numerical hulls of basic A-factor block circulant matrices. These are block companion matrices of particular simple monic matrix polynomials. By studying the polynomial numerical hulls of the Kronecker product of two matrices, we characterize the polynomial numerical hulls of unitary basic A-factor block circulant matrices.     

Relations Between M?bius and Coboundary Polynomials

It is known that, in general, the coboundary polynomial and the M?bius polynomial of a matroid do not determine each other. Less is known about more specific cases. In this paper, we will investigate if it is possible that the M?bius polynomial of a matroid, together with the M?bius polynomial of the dual matroid, define the coboundary polynomial of the matroid. In some cases, the answer is affirmative, and we will give two constructions to determine the coboundary polynomial in these cases.     

多项式方程组的主项解耦消元法

本文提出多项式组符号求解的主项解耦 (主项只含主元 )消元法 :视多项式为变元不同幂积的线性组合 ,以主项解耦三角型多项式组 DTS为引导 ,用逐项伪除求余式 ,将多项式组 PS化为与其同解的 DTS.内容涉及 :消元算法、DTS的存在性与结构特性、零点集结构公式等 .亦对 Grobner基法、吴文俊消元法与本文方法之间的相互联系、区别以及特点进行了比较 .研究表明主项解耦消元法适用于一般多项式组且效率较高     

A note on the matching numbers of triangle-free graphs

For the sake of brevity the absolute values of the coefficients of the matching polynomial of a graph are called matching numbers in this note. It is shown that for a triangle-free graph these numbers coincide with the coefficients of the chromatic polynomial of its complement when this polynomial is written in factorial form. As an application it is mentioned that the coefficients of every rook polynomial are at the same time coefficients of some chromatic polynomial.     

The Complexity of Computing the Hilbert Polynomial of Smooth Equidimensional Complex Projective Varieties

We continue the study of counting complexity begun in [13], [14], [15] by proving upper and lower bounds on the complexity of computing the Hilbert polynomial of a homogeneous ideal. We show that the problem of computing the Hilbert polynomial of a smooth equidimensional complex projective variety can be reduced in polynomial time to the problem of counting the number of complex common zeros of a finite set of multivariate polynomials. The reduction is based on a new formula for the coefficients of the Hilbert polynomial of a smooth variety. Moreover, we prove that the more general problem of computing the Hilbert polynomial of a homogeneous ideal is polynomial space hard. This implies polynomial space lower bounds for both the problems of computing the rank and the Euler characteristic of cohomology groups of coherent sheaves on projective space, improving the #P-lower bound in Bach [1].     

On the Tutte–Krushkal–Renardy polynomial for cell complexes

Recently V. Krushkal and D. Renardy generalized the Tutte polynomial from graphs to cell complexes. We show that evaluating this polynomial at the origin gives the number of cellular spanning trees in the sense of A. Duval, C. Klivans, and J. Martin. Moreover, after a slight modification, the Tutte–Krushkal–Renardy polynomial evaluated at the origin gives a weighted count of cellular spanning trees, and therefore its free term can be calculated by the cellular matrix-tree theorem of Duval et al. In the case of cell decompositions of a sphere, this modified polynomial satisfies the same duality identity as the original polynomial. We find that evaluating the Tutte–Krushkal–Renardy along a certain line gives the Bott polynomial. Finally we prove skein relations for the Tutte–Krushkal–Renardy polynomial.