Search

A new way to formulate the notions of minimal basis and minimal indices is developed in this paper, based on the concept of a filtration of a vector space. The goal is to provide useful new tools for working with these important concepts, as well as to gain deeper insight into their fundamental nature. This approach also readily reveals a strong minimality property of minimal indices, from which follows a characterization of the vector polynomial bases in rational vector spaces. The effectiveness of this new formulation is further illustrated by proving several fundamental properties: the invariance of the minimal indices of a matrix polynomial under field extension, the direct sum property of minimal indices, the polynomial linear combination property, and the predictable degree property.

International audience; We rely on aggregate separation bounds for univariate polynomials to introduce novel worst-case separation bounds for the isolated roots of zero-dimensional, positive-dimensional, and overde- termined polynomial systems. We exploit the structure of the given system, as well as bounds on the height of the sparse (or toric) resultant, by means of mixed volume, thus establishing adaptive bounds. Our bounds improve upon Canny’s Gap theorem [9]. Moreover, they exploit sparseness and they apply without any assumptions on the input polynomial system. To evaluate the quality of the bounds, we present polynomial systems whose root separation is asymptotically not far from our bounds.We apply our bounds to three problems. First, we use them to estimate the bitsize of the eigenvalues and eigenvectors of an integer matrix; thus we provide a new proof that the problem has polynomial bit complexity. Second, we bound the value of a positive polynomial over the simplex: we improve by at least one order of magnitude upon all existing bounds. Finally, we asymptotically bound the number of steps of any purely subdivision-based algorithm that isolates all real roots of a polynomial system.

International audience; Assuming the variety of a polynomial set is invariant under a group action, we construct a set of invariants that define the same variety. Our construction can be seen as a generalization of the previously known construction for finite groups. The result though has to be understood outside an invariant variety which is independent of the polynomial set considered. We introduce the symmetrizations of a polynomial that are polynomials in a generating set of rational invariants. The generating set of rational invariants and the symmetrizations are constructed w.r.t. a section to the orbits of the group action.

This paper presents a method for designing inputs to identify linear continuous-time multiple-input multiple-output (MIMO) systems. The goal here is to design a T-optimal band-limited spectrum satisfying certain input/output power constraints. The input power spectral density matrix is parametrized as the product $$\phi_u(\text{j}\omega)=\frac{1}{2}H(\text{j}\omega)H^\text{H}(\text{j}\omega)$$ , where H(jω) is a matrix polynomial. This parametrization transforms the T-optimal cost function and the constraints into a quadratically constrained quadratic program (QCQP). The QCQP turns out to be a non-convex semidefinite program with a rank one constraint. A convex relaxation of the problem is first solved. A rank one solution is constructed from the solution to the relaxed problem. This relaxation admits no gap between its solution and the original non-convex QCQP problem. The constructed rank one solution leads to a spectrum that is optimal. The proposed input design methodology is experimentally validated on a cantilever beam bonded with piezoelectric plates for sensing and actuation. Subspace identification algorithm is used to estimate the system from the input-output data.

In this paper, we investigate the sample size requirement for exact recovery of a high order tensor of low rank from a subset of its entries. We show that a gradient descent algorithm with initial value obtained from a spectral method can, in particular, reconstruct a ${d\times d\times d}$ tensor of multilinear ranks $(r,r,r)$ with high probability from as few as $O(r^{7/2}d^{3/2}\log^{7/2}d+r^7d\log^6d)$ entries. In the case when the ranks $r=O(1)$, our sample size requirement matches those for nuclear norm minimization (Yuan and Zhang, 2016a), or alternating least squares assuming orthogonal decomposability (Jain and Oh, 2014). Unlike these earlier approaches, however, our method is efficient to compute, easy to implement, and does not impose extra structures on the tensor. Numerical results are presented to further demonstrate the merits of the proposed approach., 56 pages, 4 figures

The combinatorics of walks on a graph is a key topic in network science. Here we study a special class of walks on directed graphs. We combine two features that have previously been considered in isolation. We consider alternating walks, which form the basis of algorithms for hub/authority detection and for discovering directed bipartite substructure. Within this class, we restrict to non-backtracking walks, since this constraint has been seen to offer advantages in related contexts. We derive a recursive formula for counting the total number of non-backtracking alternating walks of a given length, leading to an expression for any associated power series expansion. We discuss computational issues for the widely used cases of resolvent and exponential series, showing that non-backtracking can be incorporated at very little extra cost. We also derive an appropriate asymptotic limit which gives a parameter-free, spectral analogue. We perform tests on an artificial data set in order to quantify the advantages of the new methodology. We also show that the removal of backtracking allows us to identify larger bipartite subgraphs within an anatomical connectivity network from neuroscience.

In this paper we deal with ordinary differential equations of the form dy/dx = P(x, y) where P(x, y) is a real polynomial in the variables x and y, of degree n in the variable y. If y = φ(x) is a solution of this equation defined for x ∈ [0, 1] and which satisfies φ(0) = φ(1), we say that it is a periodic orbit. A limit cycle is an isolated periodic orbit in the set of all periodic orbits. If φ(x) is a polynomial, then φ(x) is called a polynomial solution.

In this paper we determine the maximum number of polynomial solutions of Bernoulli differential equations and of some integrable polynomial Abel differential equations. As far as we know, the tools used to prove our results have not been utilized before for studying this type of questions. We show that the addressed problems can be reduced to know the number of polynomial solutions of a related polynomial equation of arbitrary degree. Then we approach to these equations either applying several tools developed to study extended Fermat problems for polynomial equations, or reducing the question to the computation of the genus of some associated planar algebraic curves.

Based on unique decoding of the polynomial residue code with non-pairwise coprime moduli, a polynomial with degree less than that of the least common multiple (lcm) of all the moduli can be accurately reconstructed when the number of residue errors is less than half the minimum distance of the code. However, once the number of residue errors is beyond half the minimum distance of the code, the unique decoding may fail and lead to a large reconstruction error. In this paper, assuming that all the residues are allowed to have errors with small degrees, we consider how to reconstruct the polynomial as accurately as possible in the sense that a reconstructed polynomial is obtained with only the last $\tau$ number of coefficients being possibly erroneous, when the residues are affected by errors with degrees upper bounded by $\tau$. In this regard, we first propose a multi-level robust Chinese remainder theorem (CRT) for polynomials, namely, a trade-off between the dynamic range of the degree of the polynomial to be reconstructed and the residue error bound $\tau$ is formulated. Furthermore, a simple closed-form reconstruction algorithm is also proposed., Comment: 5 pages

We outline a relatively new research agenda aiming at building a new approximation paradigm by matching two distinct domains, the polynomial approximation and the exact solution of NP -hard problems by algorithms with guaranteed and non-trivial upper complexity bounds. We show how one can design approximation algorithms achieving ratios that are “forbidden” in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower than that of an exact computation.

We study the approximation of determinant for large scale matrices with low computational complexity. This paper develops a generalized stochastic polynomial approximation frame as well as a stochastic Legendre approximation algorithm to calculate log-determinants of large-scale positive definite matrices based on the prior eigenvalue distributions. The generalized frame is implemented by weighted L 2 orthogonal polynomial expansions with an efficient recursion formula and matrix–vector multiplications. So the proposed scheme is efficient both in computational complexity and data storage. Respective error bounds are given in theory which guarantee the convergence of the proposed algorithms. We illustrate the effectiveness of our method by numerical experiments on both synthetic matrices and counting spanning trees.

A necessary and sufficient condition for the existence of a non-trivial factorization of an arbitrary bivariate polynomial with integer coefficients was presented in [2]. In this paper we develop an efficient algorithm for factoring bivariate polynomials with integer coefficients. Also, we shall give a proof of the optimality of the algorithm. For a given codeword, formed by mixing up two codewords, the algorithm recovers those codewords directly by factoring corresponding bivariate polynomial. Our algorithm determines uniquely the given polynomials which are used in forming the mixture of two codewords.

We prove a necessary and sufficient condition for a function being a polynomial function over a finite, commutative, unital ring. Further, we give an algorithm running in quasilinear time that determines whether or not a function given by its function table can be represented by a polynomial, and if the answer is yes then it provides one such polynomial.

In this paper, we study the polynomial Gauss sums over finite fields, and present an analogue of Davenport–Hasse's theorem for the polynomial Gauss sums, which is a generalization of the previous result obtained by Hayes.

We define the complete numerical radius norm for homomorphisms from any operator algebra into B ( H ) \mathcal B(\mathcal H) , and show that this norm can be computed explicitly in terms of the completely bounded norm. This is used to show that if K K is a complete C C -spectral set for an operator T T , then it is a complete M M -numerical radius set, where M = 1 2 ( C + C − 1 ) M=\frac 12(C+C^{-1}) . In particular, in view of Crouzeix’s theorem, there is a universal constant M M (less than 5.6) so that if P P is a matrix polynomial and T ∈ B ( H ) T \in \mathcal B(\mathcal H) , then w ( P ( T ) ) ≤ M ‖ P ‖ W ( T ) w(P(T)) \le M \|P\|_{W(T)} . When W ( T ) = D ¯ W(T) = \overline {\mathbb D} , we have M = 5 4 M = \frac 54 .

Some results for the polynomial inequalities with restricted zeros are established with the help of a lemma proved by Dubinin. The estimates obtained, in particular, depend on the constant term and the leading coefficient of the polynomial P(z) and strengthen as well as generalize some known results earlier proved by Lax, Turan, Aziz and others.

We consider the uniqueness of an entire function and a linear differential polynomial generated by it. One of our results improves a result of Li and Yang [‘Value sharing of an entire function and its derivatives’, J. Math. Soc. Japan51(4) (1999), 781–799].

The Shannon complexity of a function system over a q-element finite field which contains m functions of n variables in the class of polarized polynomial forms is exactly evaluated: L q PPF (n,m) = q n for all n ≥ 1, m ≥ 2, and all possible odd q. It has previously been known that L2PPF (n,m) = 2 n and L3PPF (n,m) = 3 n for all n ≥ 1 and m ≥ 2.

In 1994, J. Chen, J. Gross, and R. Rieper demonstrated how to use the rank of Mohar's overlap matrix to calculate the crosscap-number distribution, that is, the distribution of the embeddings of a graph in the nonorientable surfaces. That has ever since been by far the most frequent way that these distributions have been calculated. This article introduces a way to calculate the Euler-genus polynomial of a graph, which combines the orientable and the nonorientable embeddings, without using the overlap matrix. The crosscap-number polynomial for the nonorientable embeddings is then easily calculated from the Euler-genus polynomial and the genus polynomial.

T-functions have been widely used in the design of symmetric ciphers, hash functions, and fast cryptographic primitives. Single cycle polynomial T-functions are a special category. If they are used as state transition functions of stream ciphers, the security of the generated sequences is crucial. In 2008, Kolokotronis proposed a conjecture regarding the autocorrelation function’s values of coordinate sequences generated by single cycle polynomial T-functions. In this paper, we show that the conjecture does not hold in general and prove the conditions under which it holds.

Let R be a ring and $$\delta $$ is a derivation of R. In this paper, it is proved that, under suitable conditions, the differential polynomial ring $$R[x;\delta ]$$ has the same triangulating dimension as R. Furthermore, for a piecewise prime ring, we determine a large class of the differential polynomial ring which have a generalized triangular matrix representation for which the diagonal rings are prime.

We construct a new polynomial invariant of maps (graphs embedded in closed surfaces, not necessarily orientable). Our invariant is tailored to contain as evaluations the number of local flows and local tensions taking non-identity values in any given finite group. Moreover, it 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 of the under-lying graph of the map.

Using the approximation theory notions of polynomial mesh and Dubiner distance in a compact set, we derive error estimates for total degree polynomial optimization on Chebyshev grids of the hypercube.

In this paper we completely characterize the existence of algebraic traveling wave solutions for the celebrated Kolmogorov–Petrovskii–Piskunov/Zeldovich equation. To do it, we find necessary and sufficient conditions in order that a polynomial linear differential equation has a polynomial solution and we classify all the Darboux polynomials of the planar system \(\dot{x} =y\), \(\dot{y} =-c/d y +f(x)(f'(x)+r)\) where f is a polynomial with \(\deg f \ge 2\), \(c,d>0\) and r are real constants. All results are of interest by themselves.

Continuing the previous paper, we give several data on the distribution of roots modulo primes of an irreducible polynomial, and based on them, we propose problems on the distribution.

Given multiple univariate or multivariate real polynomials f 1 , … , f n and a desired real zero z, we investigate a problem of finding the nearest polynomial f ˜ to f 1 , … , f n having z as a zero. We use a pair of norms to define the nearest polynomial. We remark that the difficulty of the problem depends on the norm pairs and give computing methods when the norm pairs consist of the p-norm and the q-norm for ( p , q ) = ( 2 , 2 ) , ( 2 , ∞ ) , and ( ∞ , ∞ ) .

Estimating the number of isolated roots of a polynomial system is not only a fundamental study theme in algebraic geometry but also an important subproblem of homotopy methods for solving polynomial systems. For the mixed trigonometric polynomial systems, which are more general than polynomial systems and rather frequently occur in many applications, the classical Bezout number and the multihomogeneous Bezout number are the best known upper bounds on the number of isolated roots. However, for the deficient mixed trigonometric polynomial systems, these two upper bounds are far greater than the actual number of isolated roots. The BKK bound is known as the most accurate upper bound on the number of isolated roots of a polynomial system. However, the extension of the definition of the BKK bound allowing it to treat mixed trigonometric polynomial systems is very difficult due to the existence of sine and cosine functions. In this paper, two new upper bounds on the number of isolated roots of a mixed trigonometric polynomial system are defined and the corresponding efficient algorithms for calculating them are presented. Numerical tests are also given to show the accuracy of these two definitions, and numerically prove they can provide tighter upper bounds on the number of isolated roots of a mixed trigonometric polynomial system than the existing upper bounds, and also the authors compare the computational time for calculating these two upper bounds.

Binary sequences with large linear complexity have been found many applications in communication systems. We determine the linear complexity of a family of p2-periodic binary sequences derived from polynomial quotients modulo an odd prime p. Results show that these sequences have high linear complexity, which means they can resist the linear attack method.

In this paper we show that a hierarchy of conic linear programming relaxations of a cone-convex polynomial programming problem converges asymptotically under a mild well-posedness condition which can easily be checked numerically for polynomials. We also establish that an additional qualification condition guarantees finite convergence of the hierarchy. Consequently, we derive convergent semi-definite programming relaxations for convex matrix polynomial programs as well as easily tractable conic linear programming relaxations for a class of pth-order cone convex polynomial programs.

We provide a list of new natural $\mathsf{VNP}$-intermediate polynomial families, based on basic (combinatorial) $\mathsf{NP}$-complete problems that are complete under parsimonious reductions. Over finite fields, these families are in $\mathsf{VNP}$, and under the plausible hypothesis $\mathsf{Mod}_p\mathsf{P} \not\subseteq \mathsf{P/poly}$, are neither $\mathsf{VNP}$-hard (even under oracle-circuit reductions) nor in $\mathsf{VP}$. Prior to this, only the Cut Enumerator polynomial was known to be $\mathsf{VNP}$-intermediate, as shown by B\"{u}rgisser in 2000. We next show that over rationals and reals, two of our intermediate polynomials, based on satisfiability and Hamiltonian cycle, are not monotone affine polynomial-size projections of the permanent. This augments recent results along this line due to Grochow. Finally, we describe a (somewhat natural) polynomial defined independent of a computation model, and show that it is $\mathsf{VP}$-complete under polynomial-size projections. This complements a recent result of Durand et al. (2014) which established $\mathsf{VP}$-completeness of a related polynomial but under constant-depth oracle circuit reductions. Both polynomials are based on graph homomorphisms. A simple restriction yields a family similarly complete for $\mathsf{VBP}$., Comment: A preliminary version to appear in CSR 2016

Let x 0, x 1, ⋯ , x n be a set of n+1 distinct real numbers (i.e., x i ≠ x j for i ≠ j) and y 0, y 1, ⋯ , y n be given real numbers; we know that there exists a unique polynomial p n (x) of degree n such that p n (x i ) = y i for i = 0, 1, ⋯ , n; p n is the interpolation polynomial for the set {(x i , y i ), i = 0, 1, ⋯ , n}. The polynomial p n (x) can be computed by using the Lagrange method or the Newton method. This paper presents a new method for computing interpolation polynomials. We will reformulate the interpolation polynomial problem and give a new algorithm for giving the solution of this problem, the recursive polynomial interpolation algorithm (RPIA). Some properties of this algorithm will be studied and some examples will also be given.

In the present paper, a system of nonhomogeneous linear difference equations with any finite number of constant delays and linear parts given by pairwise permutable matrices is considered. Representation of its solution is derived in a form of a matrix polynomial using the Z -transform. So the recent results for one and two delays, and an inductive formula for multiple delays are unified. The representation is suitable for theoretical as well as practical computations.

In this paper, we investigate the weighted polynomial approximations with several variables. Our study relates to the approximation for by weighted polynomials. Then we will estimate the degree of approximation.

In the paper, it is proved that the distribution of a measurable polynomial on an infinite-dimensional space with log-concave measure is absolutely continuous if the polynomial is not equal to a constant almost everywhere. A similar assertion is proved for analytic functions and for some other classes of functions. Properties of distributions of norms of polynomial mappings are also studied. For the space of measurable polynomial mappings of a chosen degree, it is proved that the L1-norm with respect to a log-concave measure is equivalent to the L1-norm with respect to the restriction of the measure to an arbitrarily chosen set of positive measure.

In this work, considering bi-Bazilevic functions and using theFaber polynomials, we obtain coefficient expansions for functions in this class.In certain cases, our estimates improve some of those existing coefficient bounds

A novel, remarkably neat, differential algorithm is introduced, which is suitable to evaluate all the zeros of a generic polynomial of arbitrary degree N.

We consider the resonance set of a real polynomial, i.e. the set of all the points of the coefficient space at which the polynomial has commensurable roots. The resonance set of a polynomial can be considered as a certain generalization of its discriminant set. The structure of the resonance set is useful for investigation of resonances near stationary point of a dynamical system. The constructive algorithm of computation of polynomial parametrization of the resonance set is provided. The structure of the resonance set of a polynomial of degree \(n\) is described in terms of partitions of the number \(n\). The main algorithms, described in the paper, are organized as a library of the computer algebra system \(Maple\). The description of the resonance set of a cubic polynomial is given.

In this paper, we impose restrictions on the complex coefficients of a polynomial in order to give bounds concerning the number of zeros in a specific region of the complex plane. Our results generalize and refine a good number of results in this area of research.

Polynomial chaos expansion and Gaussian mixture models are combined in a hybrid fashion to propagate state uncertainty for spacecraft with initial Gaussian errors. Polynomial chaos expansion models uncertainty by performing an expansion using orthogonal polynomials. The accuracy of polynomial chaos expansion for a given problem can be improved by increasing the order of the orthogonal polynomial expansion. The number of terms in the orthogonal polynomial expansion increases factorially with dimensionality of the problem, thereby reducing the effectiveness of the polynomial chaos expansion approach for problems of moderately high dimensionality. This paper shows a combination of Gaussian mixture model and polynomial chaos expansion, Gaussian mixture model–polynomial chaos expansion as an alternative form of the multi-element polynomial chaos expansion. Gaussian mixture model–polynomial chaos expansion reduces the overall order required to reach a desired accuracy. The initial distribution is converted to a...

In this paper we introduce a polynomial algorithm for the recognition of weakly nonnegative unit forms. The algorithm identify hypercritical restrictions testing every 9-point subset of the quadratic form associated graph. With Depth First Search strategy, we use a similar approach for the weakly positive recognition.

We introduce an equivalence relation, which is finer than the left Wiener–Hopf equivalence at infinity for polynomial matrices, and we obtain discrete invariants and a reduced form for this equivalence relation.

We first generalize to complex matrix polynomials an improvement of an upper bound by Cauchy on the zeros of complex scalar polynomials. The bound requires the unique positive root of a real scalar polynomial of the same degree as the given complex scalar or matrix polynomial. We then create a recursive procedure to represent a matrix polynomial by another matrix polynomial of larger size, but of lower degree. We apply this procedure to scalar polynomials, and then apply the generalized improved Cauchy bound to their matrix polynomial representation, often obtaining a better bound by solving a real scalar polynomial equation of significantly reduced degree.

A vertex subset WV of the graph G=(V,E) is a total dominating set if every vertex of the graph is adjacent to at least one vertex in W. The total domination polynomial is the ordinary generating function for the number of total dominating sets in the graph. We investigated some graph products for a generalization of the total domination polynomial, called the trivariate total domination polynomial. We also show that the chromatic polynomial is encoded in the independent domination polynomial of some graph products. These results have a wide applicability to other domination related graph polynomials, e.g.the domination polynomial, the independent domination polynomial or the independence polynomial.