Algorithms for checking rational roots of b-functions and their applications

The Bernstein–Sato polynomial of a hypersurface is an important object with many applications. However, its computation is hard, as a number of open questions and challenges indicate. In this paper we propose a family of algorithms called checkRoot for optimized checking whether a given rational number is a root of Bernstein–Sato polynomial and in the affirmative case, computing its multiplicity. These algorithms are used in the new approach to compute the global or local Bernstein–Sato polynomial and b-function of a holonomic ideal with respect to a weight vector. They can be applied in numerous situations, where a multiple of the Bernstein–Sato polynomial can be established. Namely, a multiple can be obtained by means of embedded resolution, for topologically equivalent singularities or using the formula of A?Campo and spectral numbers. We also present approaches to the logarithmic comparison problem and the intersection homology D-module. Several applications are presented as well as solutions to some challenges which were intractable with the classical methods. One of the main applications is the computation of a stratification of affine space with the local b-function being constant on each stratum. Notably, the algorithm we propose does not employ primary decomposition. Our results can be also applied for the computation of Bernstein–Sato polynomials for varieties. The examples in the paper have been computed with our implementation of the methods described in Singular:Plural.     

Bernstein–Sato polynomials in positive characteristic

In characteristic zero, the Bernstein–Sato polynomial of a hypersurface can be described as the minimal polynomial of the action of an Euler operator on a suitable D-module. We consider analogous D-modules in positive characteristic, and use them to define a sequence of Bernstein–Sato polynomials (corresponding to the fact that we need to consider also divided powers Euler operators). We show that the information contained in these polynomials is equivalent to that given by the F-jumping exponents of the hypersurface, in the sense of Hara and Yoshida [N. Hara, K.-i. Yoshida, A generalization of tight closure and multiplier ideals, Trans. Amer. Math. Soc. 355 (2003) 3143–3174].     

Bernstein–Sato polynomials of hyperplane arrangements

We show that the Bernstein–Sato polynomial (that is, the b-function) of a hyperplane arrangement with a reduced equation is calculable by combining a generalization of Malgrange’s formula with the theory of Aomoto complexes due to Esnault, Schechtman, Terao, Varchenko, and Viehweg in certain cases. We prove in general that the roots are greater than \(-2\) and the multiplicity of the root \(-1\) is equal to the (effective) dimension of the ambient space. We also give an estimate of the multiplicities of the roots in terms of the multiplicities of the arrangement at the dense edges, and provide a method to calculate the Bernstein–Sato polynomial at least in the case of 3 variables with degree at most 7 and generic multiplicities at most 3. Using our argument, we can terminate the proof of a conjecture of Denef and Loeser on the relation between the topological zeta function and the Bernstein–Sato polynomial of a reduced hyperplane arrangement in the 3 variable case.     

Interpolation and convergence of Bernstein-Bézier coefficients

In this paper, two ways of the proof are given for the fact that the Bernstein-Bézier coefficients (BB-coefficients) of a multivariate polynomial converge uniformly to the polynomial under repeated degree elevation over the simplex. We show that the partial derivatives of the inverse Bernstein polynomial A _n (g) converge uniformly to the corresponding partial derivatives of g at the rate 1/n. We also consider multivariate interpolation for the BB-coefficients, and provide effective interpolation formulas by using Bernstein polynomials with ridge form which essentially possess the nature of univariate polynomials in computation, and show that Bernstein polynomials with ridge form with least degree can be constructed for interpolation purpose, and thus a computational algorithm is provided correspondingly.     

Construction of Normalized B-Splines for a Family of Smooth Spline Spaces Over Powell–Sabin Triangulations

We construct a suitable B-spline representation for a family of bivariate spline functions with smoothness r≥1 and polynomial degree 3r?1. They are defined on a triangulation with Powell–Sabin refinement. The basis functions have a local support, they are nonnegative, and they form a partition of unity. The construction involves the determination of triangles that must contain a specific set of points. We further consider a number of CAGD applications. We show how to define control points and control polynomials (of degree 2r?1), and we provide an efficient and stable computation of the Bernstein–Bézier form of such splines.     

Basic Polynomial Inequalities on Intervals and Circular Arcs

We prove the right Lax-type inequality on subarcs of the unit circle of the complex plane for complex algebraic polynomials of degree n having no zeros in the open unit disk. This is done by establishing the right Bernstein–Szeg?–Videnskii type inequality for real trigonometric polynomials of degree at most n on intervals shorter than the period. The paper is closely related to recent work by B. Nagy and V. Totik. In fact, their asymptotically sharp Bernstein-type inequality for complex algebraic polynomials of degree at most n on subarcs of the unit circle is recaptured by using more elementary methods. Our discussion offers a somewhat new way to see V.S. Videnskii’s Bernstein and Markov type inequalities for trigonometric polynomials of degree at most n on intervals shorter than a period, two classical polynomial inequalities first published in 1960. A new Riesz–Schur type inequality for trigonometric polynomials is also established. Combining this with Videnskii’s Bernstein-type inequality gives Videnskii’s Markov-type inequality immediately.     

Orthogonal polynomials with respect to the sum of an arbitrary measure and a Bernstein–Szegö measure

In the present paper we study the orthogonal polynomials with respect to a measure which is the sum of a finite positive Borel measure on [0,2π] and a Bernstein–Szegö measure. We prove that the measure sum belongs to the Szegö class and we obtain several properties about the norms of the orthogonal polynomials, as well as, about the coefficients of the expression which relates the new orthogonal polynomials with the Bernstein–Szegö polynomials. When the Bernstein–Szegö measure corresponds to a polynomial of degree one, we give a nice explicit algebraic expression for the new orthogonal polynomials.     

Marcinkiewicz–Zygmund type results in multivariate domains

We investigate Marcinkiewicz–Zygmund type inequalities for multivariate polynomials on various compact domains in \({\mathbb{R}^d}\). These inequalities provide a basic tool for the discretization of the L ^p norm and are widely used in the study of the convergence properties of Fourier series, interpolation processes and orthogonal expansions. Recently Marcinkiewicz–Zygmund type inequalities were verified for univariate polynomials for the general class of doubling weights, and for multivariate polynomials on the ball and sphere with doubling weights. The main goal of the present paper is to extend these considerations to more general multidimensional domains, which in particular include polytopes, cones, spherical sectors, toruses, etc. Our approach will rely on application of various polynomial inequalities, such as Bernstein–Markov, Schur and Videnskii type estimates, and also using symmetry and rotation in order to generate results on new domains.     

A unified approach for degree reduction of polynomials in the Bernstein basis Part I: Real polynomials

The polynomials determined in the Bernstein (Bézier) basis enjoy considerable popularity and the algorithms for reducing their degree are of practical importance in computer aided design applications. On the other hand, the conversion between the Bernstein and the power basis is ill conditioned, thus only the degree reduction algorithms which may be carried out without using this conversion are of practical value. Our unified approach enables us to describe all the algorithms of this kind known in the literature, to construct a number of new ones, which are better conditioned and cheaper than some of the currently used ones, and to study the errors of all of them in a simple homogeneous way.All these algorithms can be applied componentwise to a vector-valued polynomial representing a Bézier curve. Consider the values of the derivatives, whose orders vary successively from 1 to a given number ι or κ at the start and end point, respectively, of this curve. The current algorithms allow us to preserve these points and values for ι equal to κ, the new ones do that also without the latter constraint.     

On the polynomial Lindenstrauss theorem

Under certain hypotheses on the Banach space X, we show that the set of N-homogeneous polynomials from X to any dual space, whose Aron–Berner extensions are norm attaining, is dense in the space of all continuous N-homogeneous polynomials. To this end we prove an integral formula for the duality between tensor products and polynomials. We also exhibit examples of Lorentz sequence spaces for which there is no polynomial Bishop–Phelps theorem, but our results apply. Finally we address quantitative versions, in the sense of Bollobás, of these results.     

On the degree elevation of Bernstein polynomial representation

The polynomials determined in the Bernstein (Bézier) basis enjoy considerable popularity in computer-aided design (CAD) applications. The common situation in these applications is, that polynomials given in the basis of degree n have to be represented in the basis of higher degree. The corresponding transformation algorithms are called algorithms for degree elevation of Bernstein polynomial representations. These algorithms are only then of practical importance if they do not require the ill-conditioned conversion between the Bernstein and the power basis. We discuss all the algorithms of this kind known in the literature and compare them to the new ones we establish. Some among the latter are better conditioned and not more expensive than the currently used ones. All these algorithms can be applied componentwise to vector-valued polynomial Bézier representations of curves or surfaces.     

On Constrained Markov–Nikolskii type Inequalities for k-Absolutely Monotone Polynomials

We consider a classical problem of estimating norms of higher order derivatives of an algebraic polynomial via the norms of the polynomial itself. The corresponding extremal problem for general polynomials in the uniform norm was solved by V. A. Markov. In 1926, Bernstein found the exact constant in the Markov inequality for monotone polynomials. It was shown in [3] that the order of the constants in constrained Markov–Nikolskii inequality for k-absolutely monotone polynomials is the same as in the classical one in case \({0 < p \leqq q \leqq \infty}\) . In this paper, we find the exact order for all values of \({0 < p, q \leqq \infty}\) . It turnes out that for the case q < p the constrained Markov–Nikolskii inequality is significantly better than the unconstrained one.     

An efficient algorithm for range computation of polynomials using the Bernstein form

We present a novel optimization algorithm for computing the ranges of multivariate polynomials using the Bernstein polynomial approach. The proposed algorithm incorporates four accelerating devices, namely the cut-off test, the simplified vertex test, the monotonicity test, and the concavity test, and also possess many new features, such as, the generalized matrix method for Bernstein coefficient computation, a new subdivision direction selection rule and a new subdivision point selection rule. The features and capabilities of the proposed algorithm are compared with those of other optimization techniques: interval global optimization, the filled function method, a global optimization method for imprecise problems, and a hybrid approach combining simulated annealing, tabu search and a descent method. The superiority of the proposed method over the latter methods is illustrated by numerical experiments and qualitative comparisons.     

On the generalized Ball bases

The Ball basis was introduced for cubic polynomials by Ball, and two different generalizations for higher degree m polynomials have been called the Said–Ball and the Wang–Ball basis, respectively. In this paper, we analyze some shape preserving and stability properties of these bases. We prove that the Wang–Ball basis is strictly monotonicity preserving for all m. However, it is not geometrically convexity preserving and is not totally positive for m>3, in contrast with the Said–Ball basis. We prove that the Said–Ball basis is better conditioned than the Wang–Ball basis and we include a stable conversion between both generalized Ball bases. The Wang–Ball basis has an evaluation algorithm with linear complexity. We perform an error analysis of the evaluation algorithms of both bases and compare them with other algorithms for polynomial evaluation.     

Scattered Data Fitting by Direct Extension of Local Polynomials to Bivariate Splines

We present a new scattered data fitting method, where local approximating polynomials are directly extended to smooth (C ¹ or C ²) splines on a uniform triangulation Δ (the four-directional mesh). The method is based on designing appropriate minimal determining sets consisting of whole triangles of domain points for a uniformly distributed subset of Δ. This construction allows to use discrete polynomial least squares approximations to the local portions of the data directly as parts of the approximating spline. The remaining Bernstein–Bézier coefficients are efficiently computed by extension, i.e., using the smoothness conditions. To obtain high quality local polynomial approximations even for difficult point constellations (e.g., with voids, clusters, tracks), we adaptively choose the polynomial degrees by controlling the smallest singular value of the local collocation matrices. The computational complexity of the method grows linearly with the number of data points, which facilitates its application to large data sets. Numerical tests involving standard benchmarks as well as real world scattered data sets illustrate the approximation power of the method, its efficiency and ability to produce surfaces of high visual quality, to deal with noisy data, and to be used for surface compression.     

Bézier form of dual bivariate Bernstein polynomials

Dual Bernstein polynomials of one or two variables have proved to be very useful in obtaining Bézier form of the L ₂-solution of the problem of best polynomial approximation of Bézier curve or surface. In this connection, the Bézier coefficients of dual Bernstein polynomials are to be evaluated at a reasonable cost. In this paper, a set of recurrence relations satisfied by the Bézier coefficients of dual bivariate Bernstein polynomials is derived and an efficient algorithm for evaluation of these coefficients is proposed. Applications of this result to some approximation problems of Computer Aided Geometric Design (CAGD) are discussed.     

Constrained global optimization of multivariate polynomials using Bernstein branch and prune algorithm

We propose an algorithm for constrained global optimization to tackle non-convex nonlinear multivariate polynomial programming problems. The proposed Bernstein branch and prune algorithm is based on the Bernstein polynomial approach. We introduce several new features in this proposed algorithm to make the algorithm more efficient. We first present the Bernstein box consistency and Bernstein hull consistency algorithms to prune the search regions. We then give Bernstein contraction algorithm to avoid the computation of Bernstein coefficients after the pruning operation. We also include a new Bernstein cut-off test based on the vertex property of the Bernstein coefficients. The performance of the proposed algorithm is numerically tested on 13 benchmark problems. The results of the tests show the proposed algorithm to be overall considerably superior to existing method in terms of the chosen performance metrics.     

Fast construction of constant bound functions for sparse polynomials

A new method for the representation and computation of Bernstein coefficients of multivariate polynomials is presented. It is known that the coefficients of the Bernstein expansion of a given polynomial over a specified box of interest tightly bound the range of the polynomial over the box. The traditional approach requires that all Bernstein coefficients are computed, and their number is often very large for polynomials with moderately-many variables. The new technique detailed represents the coefficients implicitly and uses lazy evaluation so as to render the approach practical for many types of non-trivial sparse polynomials typically encountered in global optimization problems; the computational complexity becomes nearly linear with respect to the number of terms in the polynomial, instead of exponential with respect to the number of variables. These range-enclosing coefficients can be employed in a branch-and-bound framework for solving constrained global optimization problems involving polynomial functions, either as constant bounds used for box selection, or to construct affine underestimating bound functions. If such functions are used to construct relaxations for a global optimization problem, then sub-problems over boxes can be reduced to linear programming problems, which are easier to solve. Some numerical examples are presented and the software used is briefly introduced.     

Computing border bases using mutant strategies

Border bases, a generalization of Gröbner bases, have actively been addressed during recent years due to their applicability to industrial problems. In cryptography and coding theory a useful application of border based is to solve zero-dimensional systems of polynomial equations over finite fields, which motivates us for developing optimizations of the algorithms that compute border bases. In 2006, Kehrein and Kreuzer formulated the Border Basis Algorithm (BBA), an algorithm which allows the computation of border bases that relate to a degree compatible term ordering. In 2007, J. Ding et al. introduced mutant strategies bases on finding special lower degree polynomials in the ideal. The mutant strategies aim to distinguish special lower degree polynomials (mutants) from the other polynomials and give them priority in the process of generating new polynomials in the ideal. In this paper we develop hybrid algorithms that use the ideas of J. Ding et al. involving the concept of mutants to optimize the Border Basis Algorithm for solving systems of polynomial equations over finite fields. In particular, we recall a version of the Border Basis Algorithm which is actually called the Improved Border Basis Algorithm and propose two hybrid algorithms, called MBBA and IMBBA. The new mutants variants provide us space efficiency as well as time efficiency. The efficiency of these newly developed hybrid algorithms is discussed using standard cryptographic examples.