Interpolation Formulas of the Lagrange Type in a Hilbert Space that are Invariant with Respect to Polynomials

In a Hilbert space, interpolation formulas of the Lagrange type that retain degrees of interpolated polynomials are constructed. The case of a Euclidean space is considered.     

On the Gap Between Positive Polynomials and SOS of Polynomials

This note investigates the gap existing between positive polynomials and sum of squares (SOS) of polynomials, which affects several analysis and synthesis tools in control systems based on polynomial SOS relaxations, and about which almost nothing is known. In particular, a matrix characterization of the PNS, that is the positive homogeneous forms that are not SOS, is proposed, which allows to show that any PNS is the vertex of an unbounded cone of PNS. Moreover, a complete parametrization of the set of PNS is introduced.     

Symmetries of Polynomials

New algorithms for determining discrete and continuous symmetries of polynomials - also known as binary forms in classical invariant theory - are presented, and implemented in MAPLE. The results are based on a new, comprehensive theory of moving frames that completely characterizes the equivalence and symmetry properties of submanifolds under general Lie group actions.     

Testing Positiveness of Polynomials

Many problems in mathematics, logic, computer science, and engineering can be reduced to the problem of testing positiveness of polynomials (over real numbers). Although the problem is decidable (shown by Tarski in 1930), the general decision methods are not always practically applicable because of their high computational time requirements. Thus several partial methods were proposed in the field of term rewriting systems. In this paper, we exactly determine how partial these methods are, and we propose simpler and/or more efficient methods with the same power.     

Nearest Singular Polynomials

The nearest singular polynomial with a multiple zero of multiplicity k ≥ 2 is considered based on the minimization of a quadratic form. Some recursive relations between the polynomials determining the multiple zeros for consecutive k's are presented.     

Computing Sparse Multiples of Polynomials

We consider the problem of finding a sparse multiple of a polynomial. Given f??F[x] of degree d over a field F, and a desired sparsity t, our goal is to determine if there exists a multiple h??F[x] of f such that h has at most t non-zero terms, and if so, to find such an h. When F=? and t is constant, we give an algorithm which requires polynomial-time in d and the size of coefficients in h. When F is a finite field, we show that the problem is at least as hard as determining the multiplicative order of elements in an extension field of F (a problem thought to have complexity similar to that of factoring integers), and this lower bound is tight when t=2.     

Accelerated Genetic Programming of Polynomials

An accelerated polynomial construction technique for genetic programming is proposed. This is a horizontal technique for gradual expansion of a partial polynomial during traversal of its tree-structured representation. The coefficients of the partial polynomial and the coefficient of the new term are calculated by a rapid recurrent least squares (RLS) fitting method. When used for genetic programming (GP) of polynomials this technique enables us not only to achieve fast estimation of the coefficients, but also leads to power series models that differ from those of traditional Koza-style GP and from those of the previous GP with polynomials STROGANOFF. We demonstrate that the accelerated GP is sucessful in that it evolves solutions with greater generalization capacity than STROGANOFF and traditional GP on symbolic regression, pattern recognition, and financial time-series prediction tasks.     

矩阵多项式特征值的计算

提出计算矩阵多项式特征值的两种方法,搜索法和逐步递推求出全部特征值法,所得结果为研究线性多变量系统动态特性提供了一种有效的工程计算方法。     

插值方法对GIS土壤养分插值结果的影响

精准农业技术的应用越来越受到大家的关注,通过对一个地块土壤养分进行详细栅格采样化验分析,利用反距离法和克里格(Kriging)两种不同计算机插值方法对土壤中各种营养元素进行了分析研究。在采样栅格大小不同的条件下,随机选择5个采样点插值,分析对比了5个采样点在不同栅格采样条件下利用两种插值方法的插值结果。通过插值计算得到土壤中全氮、速效氮和速效磷在采样栅格较小的情况下,由于反距离法考虑的周围点数较多,插值点处的插值误差要较克里格插值总体上来讲误差小,而随着采样栅格距离的加大,克里格插值的误差要小于反距离法插值的误差。     

Verified Computation of Fast Decreasing Polynomials

In this paper the problem of verified numerical computation of algebraic fast decreasing polynomials approximating the Dirac delta function is considered. We find the smallest degree of the polynomials and give precise estimates for this degree. It is shown that the computer algebra system Maple does not always graph such polynomials reliably because of evaluating the expressions in usual floating-point arithmetic. We propose a procedure for verified computation of the polynomials and use it to produce their correct graphic presentation in Maple.     

Hurwitz多项式的新结果

本文给出了判别Hurwitz多项式的简便而又宽裕的方法,并推导了Routh判据的等价形式.     

Homogeneous Formulas and Symmetric Polynomials

We investigate the arithmetic formula complexity of the elementary symmetric polynomials S^k_n{S^k_n} . We show that every multilinear homogeneous formula computing S^k_n{S^k_n} has size at least k^W(logk)n{k^{\Omega(\log k)}n} , and that product-depth d multilinear homogeneous formulas for S^k_n{S^k_n} have size at least 2^W(k1/d)n{2^{\Omega(k^{1/d})}n} . Since Sⁿ_2n{S^{n}_{2n}} has a multilinear formula of size O(n ²), we obtain a superpolynomial separation between multilinear and multilinear homogeneous formulas. We also show that S^k_n{S^k_n} can be computed by homogeneous formulas of size k^O(logk)n{k^{O(\log k)}n} , answering a question of Nisan and Wigderson. Finally, we present a superpolynomial separation between monotone and non-monotone formulas in the noncommutative setting, answering a question of Nisan.     

基于混合插值样条的保边缘图像插值算法

结合混合插值样条(BIS)性质的特点,给出一类新的自适应图像插值算法。该方法可满足任意正实数倍的放缩要求,由于采用单核处理,而且插值像素点时无需求解方程组,因此计算复杂性较小。同时采用弹性边界的方法可以有效保持边缘像素原有特征。实验结果表明,该方法与三次多项式样条方法相比,具有更清晰的边界。     

Fast Recursive Computation of Krawtchouk Polynomials

Krawtchouk polynomials (KPs) and their moments are used widely in the field of signal processing for their superior discriminatory properties. This study proposes a new fast recursive algorithm to compute Krawtchouk polynomial coefficients (KPCs). This algorithm is based on the symmetry property of KPCs along the primary and secondary diagonals of the polynomial array. The \(n-x\) plane of the KP array is partitioned into four triangles, which are symmetrical across the primary and secondary diagonals. The proposed algorithm computes the KPCs for only one triangle (partition), while the coefficients of the other three triangles (partitions) can be computed using the derived symmetry properties of the KP. Therefore, only N / 4 recursion times are required. The proposed algorithm can also be used to compute polynomial coefficients for different values of the parameter p in interval (0, 1). The performance of the proposed algorithm is compared with that in previous literature in terms of image reconstruction error, polynomial size, and computation cost. Moreover, the proposed algorithm is applied in a face recognition system to determine the impact of parameter p on feature extraction ability. Simulation results show that the proposed algorithm has a remarkable advantage over other existing algorithms for a wide range of parameters p and polynomial size N, especially in reducing the computation time and the number of operations utilized.     

二次曲线的多项式逼近

研究用B啨ｚｉｅｒ曲线或样条逼近任意长二次曲线弧的方法 对不同曲线类型 ,均得到具有 6阶逼近精度的误差函数 并且相邻的B啨ｚｉｅｒ曲线间ＧＣ1连续 最后给出任意二次曲线弧近似多项式或多项式样条参数化的算法     

椭球的高精度多项式逼近

给出了用双三次多项式逼近椭球的一种简明方法.逼近椭圆的误差为273×10^-6,逼近椭球的误差为545×10^-6     

On Approximate GCDs of Univariate Polynomials

In this paper, we consider computations involving polynomials with inexact coefficients, i.e. with bounded coefficient errors. The presence of input errors changes the nature of questions traditionally asked in computer algebra. For instance, given two polynomials, instead of trying to compute their greatest common divisor, one might now try to compute a pair of polynomials with a non-trivial common divisor close to the input polynomials. We consider the problem of finding approximate common divisors in the context of inexactly specified polynomials. We develop efficient algorithms for the so-called nearest common divisor problem and several of its variants.     

鲁棒Hurwitz多项式的频域解释

本文用频域方法分析了鲁棒Hurwitz多项式,提出了一个判别Hurwitz多项式的充分必要条件,进而给出了Kharitonov定理和Hermitc-Bicbler定理的频域解释。对次数较低的多项式族,Kharitonov多项式的数目可以减少这一结论,本文也进行了讨论。