Sums of sets of lattice points and unimodular coverings of polytopes

If P is a lattice polytope (that is, the convex hull of a finite set of lattice points in \({\mathbf{R}^n}\)), then every sum of h lattice points in P is a lattice point in the h-fold sumset hP. However, a lattice point in the h-fold sumset hP is not necessarily the sum of h lattice points in P. It is proved that if the polytope P is a union of unimodular simplices, then every lattice point in the h-fold sumset hP is the sum of h lattice points in P.     

Gaussian rules on unbounded intervals

A quadrature rule as simple as the classical Gauss formula, with a lower computational cost and having the same convergence order of best weighted polynomial approximation in L¹ is constructed to approximate integrals on unbounded intervals. An analogous problem is discussed in the case of Lagrange interpolation in weighted L² norm. The order of convergence in our results is the best in the literature for the considered classes of functions.     

Order h4 difference methods for a class of singular two space elliptic boundary value problems

In this article, we derive difference methods of O(h⁴) for solving the system of two space nonlinear elliptic partial differential equations with variable coefficients having mixed derivatives on a uniform square grid using nine grid points. We obtain two sets of fouth-order difference methods; one in the absence of mixed derivatives, second when the coefficients of u_xy are not equal to zero and the coefficients of u_xx and u_yy are equal. There do not exist fourth-order schemes involving nine grid points for the general case. The method having two variables has been tested on two-dimensional viscous, incompressible steady-state Navier-Stokes' model equations in polar coordinates. The proposed difference method for scalar equation is also applied to the Poisson's equation in polar coordinates. Some numerical examples are provided to illustrate the fourth-order convergence of the proposed methods.     

On the number of lattice points in a small sphere and a recursive lattice decoding algorithm

Let L be a lattice in ${\mathbb{R}^n}$ . This paper provides two methods to obtain upper bounds on the number of points of L contained in a small sphere centered anywhere in ${\mathbb{R}^n}$ . The first method is based on the observation that if the sphere is sufficiently small then the lattice points contained in the sphere give rise to a spherical code with a certain minimum angle. The second method involves Gaussian measures on L in the sense of Banaszczyk (Math Ann 296:625–635, 1993). Examples where the obtained bounds are optimal include some root lattices in small dimensions and the Leech lattice. We also present a natural decoding algorithm for lattices constructed from lattices of smaller dimension, and apply our results on the number of lattice points in a small sphere to conclude on the performance of this algorithm.     

Algorithms for computing the global infimum and minimum of a polynomial function

By catching the so-called strictly critical points,this paper presents an effective algorithm for computing the global infimum of a polynomial function.For a multivariate real polynomial f ,the algorithm in this paper is able to decide whether or not the global infimum of f is finite.In the case of f having a finite infimum,the global infimum of f can be accurately coded in the Interval Representation.Another usage of our algorithm to decide whether or not the infimum of f is attained when the global infimum of f is finite.In the design of our algorithm,Wu’s well-known method plays an important role.     

A Second Look at the Toric h-Polynomial of a Cubical Complex

We provide an explicit formula for the toric h-contribution of each cubical shelling component, and a new combinatorial model to prove Chan??s result on the non-negativity of these contributions. Our model allows for a variant of the Gessel-Shapiro result on the g-polynomial of the cubical lattice, this variant may be shown by simple inclusion-exclusion. We establish an isomorphism between our model and Chan??s model and provide a reinterpretation in terms of noncrossing partitions. By discovering another variant of the Gessel-Shapiro result in the work of Denise and Simion, we find evidence that the toric h-polynomials of cubes are related to the Morgan-Voyce polynomials via Viennot??s combinatorial theory of orthogonal polynomials.     

Existence of densities of solutions of stochastic differential equations by Malliavin calculus

I considered if solutions of stochastic differential equations have their density or not when the coefficients are not Lipschitz continuous. However, when stochastic differential equations whose coefficients are not Lipschitz continuous, the solutions would not belong to Sobolev space in general. So, I prepared the class Vh which is larger than Sobolev space, and considered the relation between absolute continuity of random variables and the class Vh. The relation is associated to a theorem of N. Bouleau and F. Hirsch. Moreover, I got a sufficient condition for a solution of stochastic differential equation to belong to the class Vh, and showed that solutions of stochastic differential equations have their densities in a special case by using the class Vh.     

A simple heuristic for the p-centre problem

We describe a simple heuristic for determining the p-centre of a finite set of weighted points in an arbitrary metric space. The computational effort is O(np) for an n-point set. We show that the ratio of the objective function value of the heuristic solution to that of the optimum is bounded by min(3, 1 + α), where α is the maximum weight divided by the minimum weight of points in the set.     

Multidimensional pseudo-spectral methods on lattice grids

When multidimensional functions are approximated by a truncated Fourier series, the number of terms typically increases exponentially with the dimension s. However, for functions with more structure than just being L²-integrable, the contributions from many of the Ns terms in the truncated Fourier series may be insignificant. In this paper we suggest a way to reduce the number of terms by omitting the insignificant ones. We then show how lattice rules can be used for approximating the associated Fourier coefficients, allowing a similar reduction in grid points as in expansion terms. We also show that using a lattice grid permits the efficient computation of the Fourier coefficients by the FFT algorithm. Finally we assemble these ideas into a pseudo-spectral algorithm and demonstrate its efficiency on the Poisson equation.     

Lattice polytopes of degree 2

A theorem of Scott gives an upper bound for the normalized volume of lattice polygons with exactly i>0 interior lattice points. We will show that the same bound is true for the normalized volume of lattice polytopes of degree 2 even in higher dimensions. In particular, there is only a finite number of quadratic polynomials with fixed leading coefficient being the h^∗-polynomial of a lattice polytope.     

Universal inequalities in Ehrhart theory

In this paper, we show the existence of universal inequalities for the h*-vector of a lattice polytope P, that is, we show that there are relations among the coefficients of the h*-polynomial that are independent of both the dimension and the degree of P. More precisely, we prove that the coefficients h* ₁ and h* ₂ of the h*-vector (h* ₀, h* ₁,..., h* _d) of a lattice polytope of any degree satisfy Scott’s inequality if h* ₃ = 0.     

Global minimization of multivariate polynomials using nonstandard methods

The purpose of this paper is to present two algorithms for global minimization of multivariate polynomials. For a multivariate real polynomial f, we provide an effective algorithm for deciding whether or not the infimum of f is finite. In the case of f having a finite infimum, the infimum of f can be accurately coded as (h; a, b), where h is a real polynomial in one variable, a and b is two rational numbers with a?<?b, and (h, a, b) stands for the only real root of h in the open interval ]a, b[. Moreover, another algorithm is provided to decide whether or not the infimum of f is attained when the infimum of f is finite. Our methods are called ??nonstandard??, because an infinitesimal element is introduced in our arguments.     

Density rate of a set, application to rectifiability results for measurable jets

In this work, we present some new results concerning the sets of h-density points and their application in the context of the Whitney extension theorem. In particular, we establish a simple relation between the amount of density of a set E at x and the property that u φ _E has derivative of order h at x in the L ^p sense whenever u is continuous at x. Moreover we prove Whitney-type rectifiability results for measurable jets restricted to sets of high density points in its domain. It’s worth mentioning the case when the domain is a locally finite perimeter set.     

A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems

In this paper we present a genetic algorithm-based heuristic especially for the weighted maximum independent set problem (IS). The proposed approach treats also some equivalent combinatorial optimization problems. We introduce several modifications to the basic genetic algorithm, by (i) using a crossover called two-fusion operator which creates two new different children and (ii) replacing the mutation operator by the heuristic-feasibility operator tailored specifically for the weighted independent set. The performance of our algorithm was evaluated on several randomly generated problem instances for the weighted independent set and on some instances of the DIMACS Workshop for the particular case: the unweighted maximum clique problem. Computational results show that the proposed approach is able to produce high-quality solutions within reasonable computational times. This algorithm is easily parallelizable and this is one of its important features.     

Competitive clustering algorithms based on ultrametric properties

We propose in this paper two new competitive unsupervised clustering algorithms: the first algorithm deals with ultrametric data, it has a computational cost of O(n). The second algorithm has two strong features: it is fast and flexible on the processed data type as well as in terms of precision. The second algorithm has a computational cost, in the worst case, of O(n²), and in the average case, of O(n). These complexities are due to exploitation of ultrametric distance properties. In the first method, we use the order induced by an ultrametric in a given space to demonstrate how we can explore quickly data proximity. In the second method, we create an ultrametric space from a sample data, chosen uniformly at random, in order to obtain a global view of proximities in the data set according to the similarity criterion. Then, we use this proximity profile to cluster the global set. We present an example of our algorithms and compare their results with those of a classic clustering method.     

A non-uniform basis order for the discontinuous Galerkin method of the acoustic and elastic wave equations

Here, we solve the time-dependent acoustic and elastic wave equations using the discontinuous Galerkin method for spatial discretization and the low-storage Runge-Kutta and Crank-Nicolson methods for time integration. The aim of the present paper is to study how to choose the order of polynomial basis functions for each element in the computational mesh to obtain a predetermined relative error. In this work, the formula 2p+1≈κhk, which connects the polynomial basis order p, mesh parameter h, wave number k, and free parameter κ, is studied. The aim is to obtain a simple selection method for the order of the basis functions so that a relatively constant error level of the solution can be achieved. The method is examined using numerical experiments. The results of the experiments indicate that this method is a promising approach for approximating the degree of the basis functions for an arbitrarily sized element. However, in certain model problems we show the failure of the proposed selection scheme. In such a case, the method provides an initial basis for a more general p-adaptive discontinuous Galerkin method.     

The DH/KD algorithm: a hybrid approach for unconstrained two-dimensional cutting problems

We study both weighted and unweighted unconstrained two-dimensional guillotine cutting problems. We develop a hybrid approach which combines two heuristics from the literature. The first one (DH) uses a tree-search procedure introducing two strategies: Depth-first search and Hill-climbing. The second one (KD) is based on a series of one-dimensional Knapsack problems using Dynamic programming techniques. The DH /KD algorithm starts with a good initial lower bound obtained by using the KD algorithm. At each level of the tree-search, the proposed algorithm uses also the KD algorithm for constructing new lower bounds and uses another one-dimensional knapsack for constructing refinement upper bounds. The resulting algorithm can be seen as a generalization of the two heuristics and solves large problem instances very well within small computational time. Our algorithm is compared to Morabito et al.'s algorithm (the unweighted case), and to Beasley's [2] approach (the weighted case) on some examples taken from the literature as well as randomly generated instances.     

h-Vectors of Gorenstein polytopes

We show that the Ehrhart h-vector of an integer Gorenstein polytope with a regular unimodular triangulation satisfies McMullen's g-theorem; in particular, it is unimodal. This result generalizes a recent theorem of Athanasiadis (conjectured by Stanley) for compressed polytopes. It is derived from a more general theorem on Gorenstein affine normal monoids M: one can factor K[M] (K a field) by a “long” regular sequence in such a way that the quotient is still a normal affine monoid algebra. This technique reduces all questions about the Ehrhart h-vector of P to the Ehrhart h-vector of a Gorenstein polytope Q with exactly one interior lattice point, provided each lattice point in a multiple cP, c∈N, can be written as the sum of c lattice points in P. (Up to a translation, the polytope Q belongs to the class of reflexive polytopes considered in connection with mirror symmetry.) If P has a regular unimodular triangulation, then it follows readily that the Ehrhart h-vector of P coincides with the combinatorial h-vector of the boundary complex of a simplicial polytope, and the g-theorem applies.     

The role of BMOA in the boundedness of weighted composition operators

Boundedness (resp. compactness) of weighted composition operators Wh,φ acting on the classical Hardy space H² as Wh,φf=h(f○φ) are characterized in terms of a Nevanlinna counting function associated to the symbols h and φ whenever h∈BMOA (resp. h∈VMOA). Analogous results are given for Hp spaces and the scale of weighted Bergman spaces. In the latter case, BMOA is replaced by the Bloch space (resp. VMOA by the little Bloch space).     

Computing units in certain orders of algebraic integers

An algorithm is presented for computing units in Z[α] where α is a real root of a monic irreducible polynomial with integer coefficients. It is shown that there exist lines in the additive lattice of Z[α] which have an infinite number of units in any cylinder with one of these lines as axis. The cubic case is studied in greater detail.