Rational Ehrhart quasi-polynomials

Ehrhart?s famous theorem states that the number of integral points in a rational polytope is a quasi-polynomial in the integral dilation factor. We study the case of rational dilation factors. It turns out that the number of integral points can still be written as a rational quasi-polynomial. Furthermore, the coefficients of this rational quasi-polynomial are piecewise polynomial functions and related to each other by derivation.     

Weighted Ehrhart theory and orbifold cohomology

We introduce the notion of a weighted δ-vector of a lattice polytope. Although the definition is motivated by motivic integration, we study weighted δ-vectors from a combinatorial perspective. We present a version of Ehrhart Reciprocity and prove a change of variables formula. We deduce a new geometric interpretation of the coefficients of the Ehrhart δ-vector. More specifically, they are sums of dimensions of orbifold cohomology groups of a toric stack.     

Lattice Points, Dedekind Sums, and Ehrhart Polynomials of Lattice Polyhedra

Abstract. Let σ be a simplex of R ^N with vertices in the integral lattice Z ^N . The number of lattice points of mσ (={mα : α ∈ σ}) is a polynomial function L(σ,m) of m ≥ 0 . In this paper we present: (i) a formula for the coefficients of the polynomial L(σ,t) in terms of the elementary symmetric functions; (ii) a hyperbolic cotangent expression for the generating functions of the sequence L(σ,m) , m ≥ 0 ; (iii) an explicit formula for the coefficients of the polynomial L(σ,t) in terms of torsion. As an application of (i), the coefficient for the lattice n -simplex of R ⁿ with the vertices (0,. . ., 0, a _j , 0,. . . ,0) (1≤ j≤ n) plus the origin is explicitly expressed in terms of Dedekind sums; and when n=2 , it reduces to the reciprocity law about Dedekind sums. The whole exposition is elementary and self-contained.     

Lattice Points, Dedekind Sums, and Ehrhart Polynomials of Lattice Polyhedra

   Abstract. Let σ be a simplex of R ^N with vertices in the integral lattice Z ^N . The number of lattice points of mσ (={mα : α ∈ σ}) is a polynomial function L(σ,m) of m ≥ 0 . In this paper we present: (i) a formula for the coefficients of the polynomial L(σ,t) in terms of the elementary symmetric functions; (ii) a hyperbolic cotangent expression for the generating functions of the sequence L(σ,m) , m ≥ 0 ; (iii) an explicit formula for the coefficients of the polynomial L(σ,t) in terms of torsion. As an application of (i), the coefficient for the lattice n -simplex of R ⁿ with the vertices (0,. . ., 0, a _j , 0,. . . ,0) (1≤ j≤ n) plus the origin is explicitly expressed in terms of Dedekind sums; and when n=2 , it reduces to the reciprocity law about Dedekind sums. The whole exposition is elementary and self-contained.     

New Techniques for the Computation of Linear Recurrence Coefficients

The n coefficients of a fixed linear recurrence can be expressed through its m≤2n terms or, equivalently, the coefficients of a polynomial of a degree n can be expressed via the power sums of its zeros—by means of a polynomial equation known as the key equation for decoding the BCH error-correcting codes. The same problem arises in sparse multivariate polynomial interpolation and in various fundamental computations with sparse matrices in finite fields. Berlekamp's algorithm of 1968 solves the key equation by using order of n² operations in a fixed field. Several algorithms of 1975–1980 rely on the extended Euclidean algorithm and computing Padé approximation, which yields a solution in O(n(log n)² log log n) operations, though a considerable overhead constant is hidden in the “O” notation. We show algorithms (depending on the characteristic c of the ground field of the allowed constants) that simplify the solution and lead to further improvements of the latter bound, by factors ranging from order of log n, for c=0 and c>n (in which case the overhead constant drops dramatically), to order of min (c, log n), for 2≤c≤n; the algorithms use Las Vegas type randomization in the case of 2<c≤n.     

一类含有约束的变分问题中权重因子的最优选取

研究了一类含有线性对流约束的变分问题中权重因子的最优选取。在变分问题中,泛函权重因子选取的适当与否将影响数值计算的结果。针对目前权重因子选取的相对随意性,在对观测场和理想场合理假设的条件下,分别讨论了带有弱约束和强约束的变分问题,通过求解相应的Euler方程,运用矩阵理论和偏微分方程的差分方法,得到了在分析场与理想场之间方差最小意义下的客观权重因子。推证结果表明,若将带约束的变分问题的Euler方程离散成差分形式,且满足根据实际问题提出的合理假设以及差分方程稳定性条件,那么目标泛函中的权重因子在分析场与理想场的最小方差意义下存在最优选取。它们在理论上更客观可信,可以实现权重因子与数值模式、观测资料的整体协调以及各因子之间的相互协调。     

On the Determination of Quadrature Formulae of Highest Degree of Precision for Approximating Fourier Coefficients

Let Q₀(x), Q₁(x),..., Q_n(x),... be a sequence of polynomialswhich are orthogonal with respect to the inner product . In estimating the Fourier coefficients a₁ = $$\langlef,{Q}_{i}\rangle $$, it is natural to use a quadrature formulaof highest possible degree of precision to approximate $${\int}_{a}^{b}W\left(x\right)f\left(x\right)dx$$ where W(x) = w(x)Q_i(x).Since the weight function W(x) changes sign i times in (a, b),the usual results of quadrature theory do not apply. This paperdevelops a procedure which is an initial attempt to determinewhat degree of precision is attainable.     

Computation of the Coefficients Appearing in the Uniform Asymptotic Expansions of Integrals

The coefficients that appear in uniform asymptotic expansions for integrals are typically very complicated. In the existing literature, the majority of the work only give the first two coefficients. In a limited number of papers where more coefficients are given, the evaluation of the coefficients near the coalescence points is normally highly numerically unstable. In this paper, we illustrate how well‐known Cauchy‐type integral representations can be used to compute the coefficients in a very stable and efficient manner. We discuss the cases: (i) two coalescing saddles, (ii) two saddles coalesce with two branch points, and (iii) a saddle point near an endpoint of the interval of integration. As a special case of (ii), we give a new uniform asymptotic expansion for Jacobi polynomials in terms of Laguerre polynomials as that holds uniformly for z near 1. Several numerical illustrations are included.     

有限分析系数的精确计算与插值算法

有限分析法是流体计算中一种有效的数值计算方法.但是在解高雷诺数的对流扩散方程时,有限分析系数计算将相当耗时且系数本身将严重失真.本文揭示了上述困难的成因,并提出一种改进算法.首先,建立了一套高精度计算系统,并利用它精确地求出所有基点上被称为“P_e”的函数值.在实际计算中,有限分析系数可通过插值得到的“P_e”值求出.实用算法在保证计算精度的同时,大大提高了有限分析系数的计算速度.     

The Ehrhart Polynomial of the Birkhoff Polytope

The nth Birkhoff polytope is the set of all doubly stochastic n × n matrices, that is, those matrices with nonnegative real coefficients in which every row and column sums to one. A wide open problem concerns the volumes of these polytopes, which have been known for n $\leq$ 8. We present a new, complex-analytic way to compute the Ehrhart polynomial of the Birkhoff polytope, that is, the function counting the integer points in the dilated polytope. One reason to be interested in this counting function is that the leading term of the Ehrhart polynomial is—up to a trivial factor—the volume of the polytope. We implemented our methods in the form of a computer program, which yielded the Ehrhart polynomial (and hence the volume) of the ninth Birkhoff polytope, as well as the volume of the tenth Birkhoff polytope.     

Commuting Differential Operators of Rank 2 with Rational Coefficients

In this paper we find new pairs of self-adjoint commuting differential operators of rank 2 with rational coefficients and prove that any curve of genus 2 written as a hyperelliptic curve is the spectral curve of a pair of commuting differential operators with rational coefficients. We also study the case where curves of genus 3 are the spectral curves of pairs of commuting differential operators of rank 2 with rational coefficients.     

Symbolic Computation for Moments and Filter Coefficients of Scaling Functions

Algebraic relations between discrete and continuous moments of scaling functions are investigated based on the construction of Bell polynomials. We introduce families of scaling functions which are parametrized by moments. Filter coefficients of scaling functions and wavelets are computed with computer algebra methods (in particular Gröbner bases) using relations between moments. Moreover, we propose a novel concept for data compression based on parametrized wavelets.Received December 15, 2003     

Notes on the Roots of Ehrhart Polynomials

We determine lattice polytopes of smallest volume with a given number of interior lattice points. We show that the Ehrhart polynomials of those with one interior lattice point have largest roots with norm of order n², where n is the dimension. This improves on the previously best known bound n and complements a recent result of Braun where it is shown that the norm of a root of a Ehrhart polynomial is at most of order n². For the class of 0-symmetric lattice polytopes we present a conjecture on the smallest volume for a given number of interior lattice points and prove the conjecture for crosspolytopes. We further give a characterisation of the roots of Ehrhart polyomials in the three-dimensional case and we classify for n ≤ 4 all lattice polytopes whose roots of their Ehrhart polynomials have all real part -1/2. These polytopes belong to the class of reflexive polytopes.     

Ehrhart polynomials of cyclic polytopes

The Ehrhart polynomial of an integral convex polytope counts the number of lattice points in dilates of the polytope. In (Coefficients and roots of Ehrhart polynomials, preprint), the authors conjectured that for any cyclic polytope with integral parameters, the Ehrhart polynomial of it is equal to its volume plus the Ehrhart polynomial of its lower envelope and proved the case when the dimension d=2. In our article, we prove the conjecture for any dimension.     

Spectral Analysis of a Weighted Shift Operator with Unbounded Operator Coefficients

We obtain theorems on the structure of the resolvent of a weighted shift operator with unbounded operator coefficients which acts in Banach spaces of two-sided sequences of vectors.     

利用MATLAB符号计算求解双正交小波滤波器系数

给出了用MATLAB符号计算求解双正交小波的滤波器系数(有理数)的程序,并更正了某些文献中的滤波器系数中的错误.     

Computing the Ehrhart quasi-polynomial of a rational simplex

We present a polynomial time algorithm to compute any fixed number of the highest coefficients of the Ehrhart quasi-polynomial of a rational simplex. Previously such algorithms were known for integer simplices and for rational polytopes of a fixed dimension. The algorithm is based on the formula relating the th coefficient of the Ehrhart quasi-polynomial of a rational polytope to volumes of sections of the polytope by affine lattice subspaces parallel to -dimensional faces of the polytope. We discuss possible extensions and open questions.