Amortized multi-point evaluation of multivariate polynomials

The evaluation of a polynomial at several points is called the problem of multi-point evaluation. Sometimes, the set of evaluation points is fixed and several polynomials need to be evaluated at this set of points. Several efficient algorithms for this kind of “amortized” multi-point evaluation have been developed recently for the special cases of bivariate polynomials or when the set of evaluation points is generic. In this paper, we extend these results to the evaluation of polynomials in an arbitrary number of variables at an arbitrary set of points. We prove a softly linear complexity bound when the number of variables is fixed. Our method relies on a novel quasi-reduction algorithm for multivariate polynomials, that operates simultaneously with respect to several orderings on the monomials.     

Fast multivariate multi-point evaluation revisited

In 2008, Kedlaya and Umans designed the first multivariate multi-point evaluation algorithm over finite fields with an asymptotic complexity that can be made arbitrarily close to linear. However, it remains a major challenge to make their algorithm efficient for practical input sizes. In this paper, we revisit and improve their algorithm, while keeping this ultimate goal in mind. In addition we sharpen the known complexity bounds for modular composition of univariate polynomials over finite fields.     

Fast computation of generic bivariate resultants

We prove that the resultant of two “sufficiently generic” bivariate polynomials over a finite field can be computed in quasi-linear expected time, using a randomized algorithm of Las Vegas type. A similar complexity bound is proved for the computation of the lexicographical Gröbner basis for the ideal generated by the two polynomials.     

整系数多元多项式快速分解（1）——初始化算法

对于一般形式的整系数多元多项式Ｆ（ｘ１，ｘ２，…，ｘｔ）进行因式分解，通常总是首先选定一个变量，比如Ｘｔ，作为主变量，将下的因式分解转化为对关子Ｘｔ首１的，并使Ｆ＊（０，…，０，Ｘｔ）无重因式的多元多项式Ｆ＊进行分解．本文给出了这种转化的一个新算法．由此算法而得到的Ｆ＊之规模要明显地小于以前的方法的结果，从而使得进一步分解Ｆ＊以得到Ｆ的因式分解的计算时间复杂可以大大地降低．     

On Radon’s recipe for choosing correct sites for multivariate polynomial interpolation

A class of sets correct for multivariate polynomial interpolation is defined and verified, and shown to coincide with the collection of all correct sets constructible by the recursive application of Radon’s recipe, and a recent concrete recipe for correct sets is shown to produce elements in that class.     

ON SOME EXTREMAL PROPERTIES OF ALGEBRAIC POLYNOMIALS

ＯＮＳＯＭＥＥＸＴＲＥＭＡＬＰＲＯＰＥＲＴＩＥＳＯＦＡＬＧＥＢＲＡＩＣＰＯＬＹＮＯＭＩＡＬＳＸｉｅＳｉｑｉｎｇ（谢四清）（ＷｕｈａｎＩｕｓｔ．ｏｆＭａｔｈ．Ｓｃｉ．ＡｃａｄｅｍｉａＳｉｎｉｃａ．Ｗｕｈａｎ４３００７１，Ｃｈｉｎａ．）ＯＮＳＯＭＥＥＸＴ...     

Linear gradings of polynomial algebras

Let k be a field, let be a finite group. We describe linear -gradings of the polynomial algebra k[x ₁, ..., x _m ] such that the unit component is a polynomial k-algebra.      

On single-machine scheduling without intermediate delays

This paper introduces the non-idling machine constraint where no intermediate idle time between the operations processed by a machine is allowed. In its first part, the paper considers the non-idling single-machine scheduling problem. Complexity aspects are first discussed. The “Earliest Non-Idling” property is then introduced as a sufficient condition so that an algorithm solving the original problem also solves its non-idling variant. Moreover it is shown that preemptive problems do have that property. The critical times of an instance are then introduced and it is shown that when their number is polynomial, as for equal-length jobs, a polynomial algorithm solving the original problem has a polynomial variant solving its non-idling version.     

On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials

LetS be a triangulation of andf(z) = z ^d +a _d–1 z ^d–1++a ₀, a complex polynomial. LetF be the piecewise linear approximation off determined byS. For certainS, we establish an upper bound on the complexity of an algorithm which finds zeros ofF. This bound is a polynomial in terms ofn, max{a _i } _i , and measures of the sizes of simplices inS.     

On the tractability of linear tensor product problems in the worst case

It has been an open problem to derive a necessary and sufficient condition for a linear tensor product problem to be weakly tractable in the worst case. The complexity of linear tensor product problems in the worst case depends on the eigenvalues _{λi}i∈N${\left\{{\lambda }_i\right\}}_{i\in \mathbb{N}}$ of a certain operator. It is known that if _λ1=1${\lambda }_1=1$ and _λ2∈(0,1)${\lambda }_2\in (0,1)$ then _λn=o((lnn)⁻²)${\lambda }_n=o\left({(lnn)}^{-2}\right)$, as n→∞$n\to \infty$, is a necessary condition for a problem to be weakly tractable. We show that this is a sufficient condition as well.     

A new criterion for tractability of multivariate problems

Tractability of multivariate problems studies their complexity with respect to the number of variables, d$d$, and the accuracy of the solution ε$\epsilon$. Different types of tractability have been used, such as polynomial tractability and weak tractability and others. These tractability types, however, do not express the complexity with respect to the number of bits of accuracy.     

On a new kind of Birkhoff type trigonometric interpolation

In this paper we introduce a new kind of Birkhoff type interpolation of functions with period 2. We find necessary and sufficient conditions for regularity of this new interpolation problem. Moreover, a closed form expression for the interpolation polynomial is given.This work was supported by China State Major Key Project for Basic Researchers.     

The use of the stochastic arithmetic to estimate the value of interpolation polynomial with optimal degree

One of the considerable discussions in data interpolation is to find the optimal number of data which minimizes the error of the interpolation polynomial. In this paper, first the theorems corresponding to the equidistant nodes and the roots of the Chebyshev polynomials are proved in order to estimate the accuracy of the interpolation polynomial, when the number of data increases. Based on these theorems, then we show that by using a perturbation method based on the CESTAC method, it is possible to find the optimal degree of the interpolation polynomial. The results of numerical experiments are presented.     

关于一类Hermite-Fejér插值算子的平均收敛

本文给出基于{xk}_(k=0)~(n+1)的Hermite-Fejér插值算子平均收敛的一些新结论,这里x0=1,xn+1=-1,xk（k=1,2,…,n）是n阶Jacobi多项式的零点.     

Bernstein-Fan插值算子的逼近阶估计及其算法程序

本文研究了具有三角形波基函数的Bernstein-Fan值算子的收敛定理和逼近阶估计，并给出了它的算法程序。     

Weighted infinitesimal unitary bialgebras,pre-Lie,matrix algebras,and polynomial algebras

Motivated by comatrix coalgebras, we introduce the concept of a Newtonian comatrix coalgebra. We construct an infinitesimal unitary bialgebra on matrix algebras, via the construction of a suitable coproduct. As a consequence, a Newtonian comatrix coalgebra is established. Furthermore, an infinitesimal unitary Hopf algebra, under the view of Aguiar, is constructed on matrix algebras. By the close relationship between pre-Lie algebras and infinitesimal unitary bialgebras, we erect a pre-Lie algebra and a new Lie algebra on matrix algebras. Finally, a weighted infinitesimal unitary bialgebra on non-commutative polynomial algebras is also given.     

点带约束成本的最短路问题

本文提出了点带约束成本的最短路问题,证明了该问题是ＮＰ－完全的,并利用动态规划给出了一个伪多项式算法,对所有顶点约束成本相同的情况,给出了一个时间复杂性为Ｏ（ｍｎ＾２）的算法,对最小点成本最短路问题,给出了一个时间复杂性为Ｏ（ｎ＾２）的算法。