Sparse polynomial division using a heap

In 1974, Johnson showed how to multiply and divide sparse polynomials using a binary heap. This paper introduces a new algorithm that uses a heap to divide with the same complexity as multiplication. It is a fraction-free method that also reduces the number of integer operations for divisions of polynomials with integer coefficients over the rationals. Heap-based algorithms use very little memory and do not generate garbage. They can run in the CPU cache and achieve high performance. We compare our C implementation of sparse polynomial multiplication and division with integer coefficients to the routines of the Magma, Maple, Pari, Singular and Trip computer algebra systems.     

Chunky and equal-spaced polynomial multiplication

Finding the product of two polynomials is an essential and basic problem in computer algebra. While most previous results have focused on the worst-case complexity, we instead employ the technique of adaptive analysis to give an improvement in many “easy” cases. We present two adaptive measures and methods for polynomial multiplication, and also show how to effectively combine them to gain both advantages. One useful feature of these algorithms is that they essentially provide a gradient between existing “sparse” and “dense” methods. We prove that these approaches provide significant improvements in many cases but in the worst case are still comparable to the fastest existing algorithms.     

Algebraic manipulation in the Bernstein form made simple via convolutions

Traditional methods for algebraic manipulation of polynomials in Bernstein form try to obtain an explicit formula for each coefficient of the result of a given procedure, such us multiplication, arbitrarily high degree elevation, composition, or differentiation of rational functions. Whereas this strategy often furnishes involved expressions, these operations become trivial in terms of convolutions between coefficient lists if we employ the scaled Bernstein basis, which does not include binomial coefficients. We also carry over this scheme from the univariate case to multivariate polynomials, Bézier simplexes of any dimension and B-bases of other functional spaces. Examples of applications in geometry processing are provided, such as conversions between the triangular and tensor-product Bézier forms.     

A comparison of the average case numerical condition of the power and bernstein polynomial bases

The relative numerical condition of a root x ₀, of arbitrary multiplicity, of a polynomial p(x) in the power and Bernstein bases is considered. The polynomial equation p(x)=0 and the linear algebraic equation that defines the transformation between the bases are used to show that the relative numerical condition of x ₀ in the bases is strongly dependent on the numerical condition of this equation. Furthermore, as the multiplicity of x _o increases for a given polynomial order, the relative numerical condition of x ₀ approaches unity. Computational examples that illustrate the theoretical results are presented.     

A statistical approach for economization of the polynomial functions

Due to having the minimax property, Chebyshev polynomials are used today to economize the arbitrary polynomial functions. In this work, we present a statistical approach to show that, contrary to current thought, the Chebyshev polynomials of the first kind are not appropriate for economizing these polynomials if one uses this statistical approach. In this way, a numerical results section is also given to clearly prove our claim.     

Modelling of an arch dam by polynomial interpolation

Polynomial curves controlled by points as well as by the tangents in them allow for a great margin of freedom, far from the conditions implied by the use of conventional curves, in the design of free-form curves.The lofting technique, in turn, permits us to generate surfaces that include a series of given curves.The algorithms propitiated to generate these curves and surfaces are very suitable for the geometric design of the arch dam, since they provide for a design of the curves forming the horizontal arches in which the dam can conceivably be divided taking into account, besides, the angle among the tangents to the arch at its ends as well as the hillsides of the closed arch. Once these curves are designed, the facings of a dam can be generated as the surfaces involving both series of previous curves.This paper presents the geometric calculations behind the generation of both surfaces and their computerized processing, in addition to a practical example of the use of the proposed methodology.     

Subdivision methods for solving polynomial equations

This paper presents a new algorithm for solving a system of polynomials, in a domain of Rⁿ${\mathbb{R}}^n$. It can be seen as an improvement of the Interval Projected Polyhedron algorithm proposed by Sherbrooke and Patrikalakis [Sherbrooke, E.C., Patrikalakis, N.M., 1993. Computation of the solutions of nonlinear polynomial systems. Comput. Aided Geom. Design 10 (5), 379–405]. It uses a powerful reduction strategy based on univariate root finder using Bernstein basis representation and Descarte’s rule  . We analyse the behavior of the method, from a theoretical point of view, shows that for simple roots, it has a local quadratic convergence speed and gives new bounds for the complexity of approximating real roots in a box of Rⁿ${\mathbb{R}}^n$. The improvement of our approach, compared with classical subdivision methods, is illustrated on geometric modeling applications such as computing intersection points of implicit curves, self-intersection points of rational curves, and on the classical parallel robot benchmark problem.     

Sorting-based localization and stable computation of zeros of a polynomial. I

A method of stable address sorting is designed for localization and approximate computation of real and complex zeros of a polynomial. In an arbitrary domain, a software implementation of the method allows one to localize and to calculate with high accuracy all zeros of a polynomial, including the case when they are ill-separated. The vicinity of each zero dynamically decreases during localizing the boundaries of the domains of all zeros. Algorithms developed are formally described in the Object Pascal language and are implemented in the Delphi 7 environment. Some upper-bound estimates of a parallel version of the method are given. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 165–182, January–February 2007.     

A New Subdivision Algorithm for the Bernstein Polynomial Approach to Global Optimization

In this paper,an improved algorithm is proposed for unconstrained global optimization to tackle non-convex nonlinear multivariate polynomial programming problems.The proposed algorithm is based on the Bernstein polynomial approach.Novel features of the proposed algorithm are that it uses a new rule for the selection of the subdivision point,modified rules for the selection of the subdivision direction,and a new acceleration device to avoid some unnecessary subdivisions.The performance of the proposed algorithm is numerically tested on a collection of 16 test problems.The results of the tests show the proposed algorithm to be superior to the existing Bernstein algorithm in terms of the chosen performance metrics.     

A note on Gao’s algorithm for polynomial factorization

Shuhong Gao (2003) [6] has proposed an efficient algorithm to factor a bivariate polynomial f over a field F. This algorithm is based on a simple partial differential equation and depends on a crucial fact: the dimension of the polynomial solution space G associated with this differential equation is equal to the number r of absolutely irreducible factors of f. However, this holds only when the characteristic of F is either zero or sufficiently large in terms of the degree of f. In this paper we characterize a vector subspace of G for which the dimension is r, regardless of the characteristic of F, and the properties of Gao’s construction hold. Moreover, we identify a second vector subspace of G that leads to an analogous theory for the rational factorization of f.     

LMIs for constrained polynomial interpolation with application in trajectory planning

We consider an open-loop trajectory planning problem for linear systems with bound constraints originating from saturations or physical limitations. Using an algebraic approach and results on positive polynomials, we show that this control problem can be cast into a constrained polynomial interpolation problem admitting a convex linear matrix inequality (LMI) formulation.     

On problems without polynomial kernels

Kernelization is a strong and widely-applied technique in parameterized complexity. A kernelization algorithm, or simply a kernel, is a polynomial-time transformation that transforms any given parameterized instance to an equivalent instance of the same problem, with size and parameter bounded by a function of the parameter in the input. A kernel is polynomial if the size and parameter of the output are polynomially-bounded by the parameter of the input.In this paper we develop a framework which allows showing that a wide range of FPT problems do not have polynomial kernels. Our evidence relies on hypothesis made in the classical world (i.e. non-parametric complexity), and revolves around a new type of algorithm for classical decision problems, called a distillation algorithm, which is of independent interest. Using the notion of distillation algorithms, we develop a generic lower-bound engine that allows us to show that a variety of FPT problems, fulfilling certain criteria, cannot have polynomial kernels unless the polynomial hierarchy collapses. These problems include k-Path, k-Cycle, k-Exact Cycle, k-Short Cheap Tour, k-Graph Minor Order Test, k-Cutwidth, k-Search Number, k-Pathwidth, k-Treewidth, k-Branchwidth, and several optimization problems parameterized by treewidth and other structural parameters.     

A new proximity test for polynomial zeros

We combine some known techniques and results of Turan and Schönhage to improve substantially numerical performance of the computation of the minimum and the maximum distances from a fixed complex point to roots (zeros) of a fixed univariate polynomial.     

Minimal polynomial realizations

This paper studies the problem of realizing input-output maps by polynomial continuous-time systems. This study requires a careful definition of the notions of systems and differential equations on an algebraic variety. A concept of minimality is also introduced, and a uniqueness result is proved.     

Dual bases of a Bernstein polynomial basis on simplices

This paper extends the theory of dual bases of a one-variate B-spline basis to the case of Bernstein polynomials and presents methods of constructing dual bases of a Bernstein polynomial basis on a simplex from that of a one-variate polynomial basis, s{xⁱs}ⁿ_i=0 and s{B^k_i,k-i(x) = (^k_i)xⁱ(l-x)^k-i}s^k_i=0 on the interval [0,1].