Integer points in convex polyhedra - AbsoluteAstronomy.com

Study of integer points in convex polyhedra is motivated by the questions, such as "how many nonnegative integer

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

-valued solutions does a system of linear equations with nonnegative coefficients have" or "how many solutions does an integer linear program have". Counting integer points in polyhedra or other questions about them arise in representation theory

Representation theory

Representation theory is a branch of mathematics that studies abstract algebraic structures by representing their elements as linear transformations of vector spaces, and studiesmodules over these abstract algebraic structures...

, commutative algebra

Commutative algebra

Commutative algebra is the branch of abstract algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra...

, algebraic geometry

Algebraic geometry

Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...

, statistics

Statistics

Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....

, and computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

.

The set of integer points, or, more generally, the set of points of an affine lattice, in a polyhedron is called Z-polyhedron, from the mathematical notation

or Z for the set of integer numbers.

Properties

For a lattice Λ, Minkowski's theorem

Minkowski's theorem

In mathematics, Minkowski's theorem is the statement that any convex set in Rn which is symmetric with respect to the origin and with volume greater than 2n d contains a non-zero lattice point...

relates the number d(Λ) and the volume of a symmetric convex set

Convex set

In Euclidean space, an object is convex if for every pair of points within the object, every point on the straight line segment that joins them is also within the object...

S to the number of lattice points contained in S.

The number of lattice points contained in a polytope

Polytope

In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...

all of whose vertices are elements of the lattice is described by the polytope's Ehrhart polynomial

Ehrhart polynomial

In mathematics, an integral polytope has an associated Ehrhart polynomial which encodes the relationship between the volume of a polytope and the number of integer points the polytope contains...

. Formulas for some of the coefficients of this polynomial involve d(Λ) as well.

Loop optimization

In certain approaches to loop optimization

Loop optimization

In compiler theory, loop optimization plays an important role in improving cache performance, making effective use of parallel processing capabilities, and reducing overheads associated with executing loops. Most execution time of a scientific program is spent on loops...

, the set of the executions of the loop body is viewed as the set of integer points in a polyhedron defined by loop constraints.

Properties

Loop optimization

Further reading