Efficient evaluation of multivariate polynomials

In CAGD applications, the usual way to store a polynomial defined over a triangle is in the Bernstein-Bézier form, and the accepted way to evaluate it at a given point in the triangle is by the de Casteljau algorithm. In this paper we present an algorithm for evaluating Berstein-Bézier type polynomials which is significantly faster than de Casteljau. This suggests that a modified form of Bernstein-Bézier may be preferable for CAGD applications (as well as in applications of piecewise polynomials in data fitting and numerical solution of boundary-value problems).     

Bernstein-type operators which preserve polynomials

In this paper we present the sequence of linear Bernstein-type operators defined for f∈C[0,1] by B_n(f°τ⁻¹)°τ, B_n being the classical Bernstein operators and τ being any function that is continuously differentiable ∞ times on [0,1], such that τ(0)=0, τ(1)=1 and τ^′(x)>0 for x∈[0,1]. We investigate its shape preserving and convergence properties, as well as its asymptotic behavior and saturation. Moreover, these operators and others of King type are compared with each other and with B_n. We present as an interesting byproduct sequences of positive linear operators of polynomial type with nice geometric shape preserving properties, which converge to the identity, which in a certain sense improve B_n in approximating a number of increasing functions, and which, apart from the constant functions, fix suitable polynomials of a prescribed degree. The notion of convexity with respect to τ plays an important role.     

An identity for multivariate Bernstein polynomials

We prove an identity for multivariate Bernstein polynomials on simplices, which may be considered a pointwise orthogonality relation. Its integrated version provides a new representation for the polynomial dual basis of Bernstein polynomials. An identity for the reproducing kernel is used to define quasi-interpolants of arbitrary order.     

Bounds on absolute positiveness of multivariate polynomials

We propose and study a weighting framework for obtaining bounds on absolute positiveness of multivariate polynomials. It is shown that a well-known bound _BG$B_G$ by Hong is obtainable in this framework, and w.r.t. any bound in this framework _BG$B_G$ has a multiplicative overestimation which is at most linear in the number of variables. We also propose a general method to algorithmically improve any bound within the framework. In the univariate case, we derive the minimum number of weights necessary to obtain a bound with limited overestimation w.r.t. the absolute positiveness of the polynomial.     

An improved EZ-GCD algorithm for multivariate polynomials

The EZ-GCD algorithm often has the bad-zero problem, which has a remarkable influence on polynomials with higher-degree terms. In this paper, by applying special ideals, the EZ-GCD algorithm for sparse polynomials is improved. This improved algorithm greatly reduces computational complexity because of the sparseness of polynomials. The author expects that the use of these ideals will be useful as a resolution for obtaining a GCD of sparse multivariate polynomials with higher-degree terms.     

On some fractional generalizations of the Laguerre polynomials and the Kummer function

This paper refers to some generalizations of the classical Laguerre polynomials. By means of the Riemann–Liouville operator of fractional calculus and Rodrigues’ type representation formula of fractional order, the Laguerre functions are derived and some of their properties are given and compared with the corresponding properties of the classical Laguerre polynomials. Further generalizations of the Laguerre functions are introduced as a solution of a fractional version of the classical Laguerre differential equation. Likewise, a generalization of the Kummer function is introduced as a solution of a fractional version of the Kummer differential equation. The Laguerre polynomials and functions are presented as special cases of the generalized Laguerre and Kummer functions. The relation between the Laguerre polynomials and the Kummer function is extended to their fractional counterparts.     

Symbolic–numeric sparse interpolation of multivariate polynomials

We consider the problem of sparse interpolation of an approximate multivariate black-box polynomial in floating point arithmetic. That is, both the inputs and outputs of the black-box polynomial have some error, and all numbers are represented in standard, fixed-precision, floating point arithmetic. By interpolating the black box evaluated at random primitive roots of unity, we give efficient and numerically robust solutions. We note the similarity between the exact Ben-Or/Tiwari sparse interpolation algorithm and the classical Prony’s method for interpolating a sum of exponential functions, and exploit the generalized eigenvalue reformulation of Prony’s method. We analyse the numerical stability of our algorithms and the sensitivity of the solutions, as well as the expected conditioning achieved through randomization. Finally, we demonstrate the effectiveness of our techniques in practice through numerical experiments and applications.     

Approximate factorization of multivariate polynomials using singular value decomposition

We describe the design, implementation and experimental evaluation of new algorithms for computing the approximate factorization of multivariate polynomials with complex coefficients that contain numerical noise. Our algorithms are based on a generalization of the differential forms introduced by W. Ruppert and S. Gao to many variables, and use singular value decomposition or structured total least squares approximation and Gauss–Newton optimization to numerically compute the approximate multivariate factors. We demonstrate on a large set of benchmark polynomials that our algorithms efficiently yield approximate factorizations within the coefficient noise even when the relative error in the input is substantial (10⁻³).     

A new algorithm for sparse interpolation of multivariate polynomials

To reconstruct a black box multivariate sparse polynomial from its floating point evaluations, the existing algorithms need to know upper bounds for both the number of terms in the polynomial and the partial degree in each of the variables. Here we present a new technique, based on Rutishauser’s qd$qd$-algorithm, in which we overcome both drawbacks.     

On certain properties of Hurwitz determinants for interval polynomials

Consider the stable interval polynomialsF _n (z)=z ⁿ +a ₁ z ^n?1 +...+a _n?1 z+a _n wherea _i are real numbers, satisfying the inequalities α _i ≤a _i ≤β _i ,i=1,2, ...,n. In this paper we prove that mind _n (a) is the same foraεD andaεD ₁, whereD=[α₁, β₁]×[α₂, β₂]×...×[α _n , β _n ],D={(γ₁, γ₂,...γ _n )∈D:γ₁=α₁∨γ₁=β₁,... γ _n =α _n ∨γ _n =β _n }d _n (a)=detH, aεD, H—Hurwitz matrix for the polynomialF _n (z).     

基于NTL算法库的多元多项式因式分解高效实现

针对多元多项式因式分解困难问题,利用现有因式分解算法,提出了一种基于任意精度计算函数库NTL的高效多元多项式因式分解实现方法HPFMP。介绍了NTL算法库,讨论了如何运用该算法库实现高效的数论与计算代数计算;充分利用具备高效、任意精度大整数、实数的计算数论与计算代数的NTL算法库实现了多元多项式因式分解;与现有代数系统Maple11进行了对比测试,实验结果表明,该实现方法具有更高的效率。     

On multivariate interpolation by generalized polynomials on subsets of grids

This note may be regarded as a complement to a paper of H. Werner [17] who has carried over Newton's classical interpolation formula to Hermite interpolation by algebraic polynomials of several real variables on certain subsets of grids. Here generalized polynomials of several real or complex variables are treated. Recursive procedures are presented showing that interpolation by generalized multivariate polynomials is performed nearly as simply as interpolation by algebraic polynomials. Having in general the same approximation power, generalized polynomials may be better adapted to special situations. In particular, the results of this note can be used for constructing nonpolynomial finite elements since in that case the interpolation points usually are rather regular subsystems of grids. Though the frame is more general than in [17] some of our proofs are simpler. As an alternative method to evaluate multivariate generalized interpolation polynomials for rectangular grids a Neville-Aitken algorithm is presented.     

A new approach to the symbolic factorization of multivariate polynomials

A heuristic factorization scheme that uses learning and other heuristic programming techniques to improve the efficiency of determining the symbolic factorization of multivariate polynomials with integer coefficients and an arbitrary number of variables and terms is described. The learning program, POLYFACT, in which the factorization scheme is implemented is also described. POLYFACT uses learning through the dynamic construction and manipulation of first-order predicate calculus heuristics to reduce the amount of searching for the irreducible factors of a polynomial.Tables containing the results of factoring randomly generated multivariate polynomials are presented: (1) to demonstrate that learning does improve considerably the efficiency of factoring polynomials, and (2) to show that POLYFACT does learn from previous experience.The factorization times of polynomials factored by both the scheme implemented in POLYFACT and Wang's implementation of Berlekamp's algorithm are given. The two algorithms are compared, and two situations where POLYFACT'S algorithm can be used to improve the efficiency of Wang's algorithm are discussed.     

Numerical evaluation of certain hypersingular integrals using refinable operators

This paper concerns the construction of quadrature rules based on the use of suitable refinable quasi-interpolatory operators, for the numerical evaluation of Hadamard finite-part integrals. Convergence analysis of the obtained rules is developed and numerical examples are included.     

An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography

In this paper, we present an efficient and general algorithm for decomposing multivariate polynomials of the same arbitrary degree. This problem, also known as the Functional Decomposition Problem (FDP), is classical in computer algebra. It is the first general method addressing the decomposition of multivariate polynomials (any degree, any number of polynomials). As a byproduct, our approach can be also used to recover an ideal I from its kth power I^k. The complexity of the algorithm depends on the ratio between the number of variables (n) and the number of polynomials (u). For example, polynomials of degree four can be decomposed in , when this ratio is smaller than . This work was initially motivated by a cryptographic application, namely the cryptanalysis of 2R⁻ schemes. From a cryptographic point of view, the new algorithm is so efficient that the principle of two-round schemes, including 2R⁻ schemes, becomes useless. Besides, we believe that our algorithm is of independent interest.     

多元非线性多项式智能拟合法及其应用研究

提出基于矩阵法结合遗传算法的多元非线性多项式智能拟合法。该法先将多元非线性多项式转化成多元线性多项式,建立最小二乘法标准矩阵,用遗传算法对多项式的项数、各项类型、次数等进行搜索组合,得到最优的拟合函数式,从而实现智能拟合的目的。用该法拟合了金祖源乱堆填料层压降通用关联图,结果令人满意。智能拟合法与传统的非智能拟合法相比具有可以自动寻求最优多项式、拟合精度高的优点。用Visual Basic6．0编程实现智能拟合法,算法稳定,收敛速度快。     

A hybrid parallel solver for systems of multivariate polynomials using CPUs and GPUs

This paper deals with a problem of finding valid solutions to systems of polynomial constraints. Although there have been several quite successful algorithms based on domain subdivision to resolve this problem, some major issues are still demanding further research. Prime obstacles in developing an efficient subdivision-based polynomial constraint solver are the exhaustive, although hierarchical, search of the zero-set in the parameter domain, which is computationally demanding, and their scalability in terms of the number of variables. In this paper, we present a hybrid parallel algorithm for solving systems of multivariate constraints by exploiting both the CPU and the GPU multicore architectures. We dedicate the CPU for the traversal of the subdivision tree and the GPU for the multivariate polynomial subdivision. By decomposing the constraint solving technique into two different components, hierarchy traversal and polynomial subdivision, each of which is more suitable to CPUs and GPUs, respectively, our solver can fully exploit the availability of hybrid, multicore architectures of CPUs and GPUs. Furthermore, our GPU-based subdivision method takes advantage of the inherent parallelism in the multivariate polynomial subdivision. We demonstrate the efficacy and scalability of the proposed parallel solver through several examples in geometric applications, including Hausdorff distance queries, contact point computations, surface–surface intersections, ray trap constructions, and bisector surface computations. In our experiments, the proposed parallel method achieves up to two orders of magnitude improvement in performance compared to the state-of-the-art subdivision-based CPU solver.     

Uniqueness of meromorphic functions whose certain nonlinear differential polynomials share a polynomial

In this paper, we get two uniqueness theorems of meromorphic functions whose certain nonlinear differential polynomials share a polynomial. The results in this paper extend the corresponding results given by Fang (2002) in [7]. Our reasoning in this paper will correct a defective reasoning in the proof of Theorem 4 in Bhoosnurmath and Dyavanal (2007) [8]. An example is provided to show that some conditions of the main results in this paper are necessary.