一类广义Ball曲线的改进

Said将Ball基由三阶延伸到奇数阶。本文在任意阶上讨论广义Ball曲线性质及其求值的新一种递归算法。     

UNIFYING REPRESENTATION OF BEZIERCURVE AND GENERALIZED BALL CURVES

Abstract. This paper presents two new families of the generalized Ball curves which include theI~zier curve, the generalized Ball curves defined by Wang and Said independently and some in-termediate curves. The relative degree elevation and reduction schemes, recursive algorithmsand the Bernstein-Bezier representation are also given.     

Tight bounds for mixing of the Swendsen–Wang algorithm at the Potts transition point

We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice ${\mathbb{Z}^{d}}$ —heat bath dynamics and the Swendsen–Wang algorithm—and prove that, under certain circumstances, the mixing in these algorithms is torpid or slow. In particular, we show that for heat bath dynamics throughout the region of phase coexistence, and for the Swendsen–Wang algorithm at the transition point, the mixing time in a box of side length L with periodic boundary conditions has upper and lower bounds which are exponential in L ^d-1. This work provides the first upper bound of this form for the Swendsen–Wang algorithm, and gives lower bounds for both algorithms which significantly improve the previous lower bounds that were exponential in L/(log L)².     

Two new triangles of q-integers via q-Eulerian polynomials of type A and B

The classical Eulerian polynomials can be expanded in the basis t ^k?1(1+t) ^n+1?2k (1≤k≤?(n+1)/2?) with positive integral coefficients. This formula implies both the symmetry and the unimodality of the Eulerian polynomials. In this paper, we prove a q-analogue of this expansion for Carlitz’s q-Eulerian polynomials as well as a similar formula for Chow–Gessel’s q-Eulerian polynomials of type B. We shall give some applications of these two formulas, which involve two new sequences of polynomials in the variable q with positive integral coefficients. It is an open problem to give a combinatorial interpretation for these polynomials.     

On standard bases in rings of differential polynomials

We consider Ollivier’s standard bases (also known as differential Gröbner bases) in an ordinary ring of differential polynomials in one indeterminate. We establish a link between these bases and Levi’s reduction process. We prove that the ideal [x ^p ] has a finite standard basis (w.r.t. the so-called β-orderings) that contains only one element. Various properties of admissible orderings on differential monomials are studied. We bring up the question of whether there is a finitely generated differential ideal that does not admit a finite standard basis w.r.t. any ordering.     

A unified approach to evaluation algorithms for multivariate polynomials

We present a unified framework for most of the known and a few new evaluation algorithms for multivariate polynomials expressed in a wide variety of bases including the Bernstein-Bézier, multinomial (or Taylor), Lagrange and Newton bases. This unification is achieved by considering evaluation algorithms for multivariate polynomials expressed in terms of L-bases, a class of bases that include the Bernstein-Bézier, multinomial, and a rich subclass of Lagrange and Newton bases. All of the known evaluation algorithms can be generated either by considering up recursive evaluation algorithms for L-bases or by examining change of basis algorithms for L-bases. For polynomials of degree in variables, the class of up recursive evaluation algorithms includes a parallel up recurrence algorithm with computational complexity , a nested multiplication algorithm with computational complexity and a ladder recurrence algorithm with computational complexity . These algorithms also generate a new generalization of the Aitken-Neville algorithm for evaluation of multivariate polynomials expressed in terms of Lagrange L-bases. The second class of algorithms, based on certain change of basis algorithms between L-bases, include a nested multiplication algorithm with computational complexity , a divided difference algorithm, a forward difference algorithm, and a Lagrange evaluation algorithm with computational complexities , and per point respectively for the evaluation of multivariate polynomials at several points.

     

Elliptic periods for finite fields

We construct two new families of basis for finite field extensions. Bases in the first family, the so-called elliptic bases, are not quite normal bases, but they allow very fast Frobenius exponentiation while preserving sparse multiplication formulas. Bases in the second family, the so-called normal elliptic bases are normal bases and allow fast (quasi-linear) arithmetic. We prove that all extensions admit models of this kind.     

On the optimal stability of the Bernstein basis

We show that the Bernstein polynomial basis on a given interval is ``optimally stable,' in the sense that no other nonnegative basis yields systematically smaller condition numbers for the values or roots of arbitrary polynomials on that interval. This result follows from a partial ordering of the set of all nonnegative bases that is induced by nonnegative basis transformations. We further show, by means of some low--degree examples, that the Bernstein form is not uniquely optimal in this respect. However, it is the only optimally stable basis whose elements have no roots on the interior of the chosen interval. These ideas are illustrated by comparing the stability properties of the power, Bernstein, and generalized Ball bases.

     

On unconditional polynomial bases inL p and bergman spaces

In this paper we consider unconditional bases inL _p(T), 1<p<∞,p ≠ 2, consisting of trigonometric polynomials. We give a lower bound for the degree of polynomials in such a basis (Theorem 3.4) and show that this estimate is best possible. This is applied to the Littlewood-Paley-type decompositions. We show that such a decomposition has to contain exponential gaps. We also consider unconditional polynomial bases inH _p as bases in Bergman-type spaces and show that they provide explicit isomorphisms between Bergman-type spaces and natural sequences spaces.     

Fueter polynomials in discrete Clifford analysis

Discrete Clifford analysis is a higher dimensional discrete function theory, based on skew Weyl relations. The basic notions are discrete monogenic functions, i.e. Clifford algebra valued functions in the kernel of a discrete Dirac operator. In this paper, we introduce the discrete Fueter polynomials, which form a basis of the space of discrete spherical monogenics, i.e. discrete monogenic, homogeneous polynomials. Their definition is based on a Cauchy–Kovalevskaya extension principle. We present the explicit construction for this discrete Fueter basis, in arbitrary dimension m and for arbitrary homogeneity degree k.     

Computing border bases

This paper presents several algorithms that compute border bases of a zero-dimensional ideal. The first relates to the FGLM algorithm as it uses a linear basis transformation. In particular, it is able to compute border bases that do not contain a reduced Gröbner basis. The second algorithm is based on a generic algorithm by Bernard Mourrain originally designed for computing an ideal basis that need not be a border basis. Our fully detailed algorithm computes a border basis of a zero-dimensional ideal from a given set of generators. To obtain concrete instructions we appeal to a degree-compatible term ordering σ and hence compute a border basis that contains the reduced σ-Gröbner basis. We show an example in which this computation actually has advantages over Buchberger's algorithm. Moreover, we formulate and prove two optimizations of the Border Basis Algorithm which reduce the dimensions of the linear algebra subproblems.     

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.     

Limits for Szegö polynomials in frequency analysis

We characterize limits for orthogonal Szegö polynomials of fixed degree k, with respect to certain measures on the unit circle which are weakly convergent to a sum of m<k point masses. Such measures arise, for example, as a convolution of point masses with an approximate identity. It is readily seen that the underlying measures in two recently-proposed methods for estimating the m frequencies, θj, of a discrete-time trigonometric signal using Szegö polynomials are of this form. We prove existence of Szegö polynomial limits associated with a general class of weakly convergent measures, and prove that for convolution of point masses with the Poisson kernel, which underlies one of the recently-proposed methods, the limit has as a factor the Szegö polynomial with respect to a related measure, which we specify. Since m of the zeros approach the eiθj, this result uniquely characterizes the limit. A similar result is obtained for measures consisting of point masses with additive absolutely continuous part.     

The weighted dual functions for Wang-Bézier type generalized Ball bases and their applications

By introducing the inner-product matrix of two vector functions and using conversion matrix, explicit formulas for the dual basis functions of Wang-Bézier type generalized Ball bases (WBGB) with respect to the Jacobi weight function are given. The dual basis functions with and without boundary constraints are also considered. As a result, the paper includes the weighted dual basis functions of Bernstein basis, Wang-Ball basis and some intermediate bases. Dual functionals for WBGB and the least square approximation polynomials are also obtained.     

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.     

Derivation of the Real-Rootedness of Coordinator Polynomials from the Hermite–Biehler Theorem

By using the Hermite–Biehler theorem, we give a new proof of the real-rootedness of the coordinator polynomials of type D, which was recently established by Wang and Zhao. As a consequence, we also obtain the compatibility between the coordinator polynomials of type D and those of type C.     

Quantum B-splines

Quantum splines are piecewise polynomials whose quantum derivatives (i.e. certain discrete derivatives or equivalently certain divided differences) agree up to some order at the joins. Just like classical splines, quantum splines admit a canonical basis with compact support: the quantum B-splines. These quantum B-splines are the q-analogues of classical B-splines. Here quantum B-spline bases and quantum B-spline curves are investigated, using a new variant of the blossom: the q (quantum)-blossom. The q-blossom of a degree d polynomial is the unique symmetric, multiaffine function in d variables that reduces to the polynomial along the q-diagonal. By applying the q-blossom, algorithms and identities for quantum B-spline bases and quantum B-spline curves are developed, including quantum variants of the de Boor algorithms for recursive evaluation and quantum differentiation, knot insertion procedures for converting from quantum B-spline to piecewise quantum Bézier form, and a quantum variant of Marsden’s identity.     

On the Ma–Trudinger–Wang curvature on surfaces

We investigate the properties of the Ma–Trudinger–Wang nonlocal curvature tensor in the case of surfaces. In particular, we prove that a strict form of the Ma–Trudinger– Wang condition is stable under C ⁴ perturbation if the nonfocal domains are uniformly convex; and we present new examples of positively curved surfaces which do not satisfy the Ma–Trudinger–Wang condition. As a corollary of our results, optimal transport maps on a “sufficiently flat” ellipsoid are in general nonsmooth.     

Constructive D-Module Theory with Singular

We overview numerous algorithms in computational D-module theory together with the theoretical background as well as the implementation in the computer algebra system Singular. We discuss new approaches to the computation of Bernstein operators, of logarithmic annihilator of a polynomial, of annihilators of rational functions as well as complex powers of polynomials. We analyze algorithms for local Bernstein–Sato polynomials and also algorithms, recovering any kind of Bernstein–Sato polynomial from partial knowledge of its roots. We address a novel way to compute the Bernstein–Sato polynomial for an affine variety algorithmically. All the carefully selected nontrivial examples, which we present, have been computed with our implementation. We also address such applications as the computation of a zeta-function for certain integrals and revealing the algebraic dependence between pairwise commuting elements.     

Ehrhart Polynomials of Matroid Polytopes and Polymatroids

We investigate properties of Ehrhart polynomials for matroid polytopes, independence matroid polytopes, and polymatroids. In the first half of the paper we prove that, for fixed rank, Ehrhart polynomials of matroid polytopes and polymatroids are computable in polynomial time. The proof relies on the geometry of these polytopes as well as a new refined analysis of the evaluation of Todd polynomials. In the second half we discuss two conjectures about the h ^*-vector and the coefficients of Ehrhart polynomials of matroid polytopes; we provide theoretical and computational evidence for their validity.