Next: Important functions in Lattice.c
Up: Lattices
Previous: Lattices
  Contents
Lattice are manipulated in Polylib because they are used in
constructing
-polyhedra. A subset
in
is a lattice if is generated by integral combination of finitely many
vectors:
(
).
If the
vectors have integral coordinates,
is an integer lattice. If the
vectors are linearly independent,
they constitute a basis of the lattice. If the vectors
constitute a basis of
, the
lattice is said to be full dimensional.
The affine object corresponding to a lattice is called an affine
lattice. It is constructed by adding the same constant vectors to
all the points of a lattice. For instance, the set
can be interpreted as an affine
lattice: it is the lattice defined by any integral linear
combinations of the vectors
and
, plus the vector
In Polylib, only full-dimensionnal affine integral
lattices are considered. It can easily be proven that an element
of this subset of affine lattices can always be represented by a
non singular integral matrix and an integral vector. For
instance, lattice
above, will be mathematically represented
by:
The data structure used to represent an affine lattice in
Polylib is an affine matrix. For example, lattice
will be represented
in Polylib by the following matrix:
Lattice manipulation naturally leads to an intensive use of the
Hermite normal form (HNF).
Definition 3 (
Hermite normal form)
A matrix
![$A$](img8.gif)
of full row rank is said to be in Hermite normal form (HNF) if it
has the form
![$[B \ 0]$](img71.gif)
where
![$B$](img2.gif)
is a non singular, lower triangular,
non negative matrix, in which each row has a unique maximum entry
located on the main diagonal of
![$B$](img2.gif)
.
Theorem 1
For any rational matrix
![$A$](img8.gif)
of full row rank, there exists a unique
matrix
![$B$](img2.gif)
in Hermite normal form and a unimodular matrix
![$U$](img72.gif)
such that
![$A=BU$](img73.gif)
.
Consider the following matrices
,
and
. Then
is the Hermite decomposition of
.
Proposition 3
(uniqueness of the Hermite normal form)
Let
![$A$](img8.gif)
and
![$A'$](img76.gif)
be rational matrices of full row rank, with Hermite
normal forms
![$[B \ 0]$](img71.gif)
and
![$[B' \ 0]$](img77.gif)
, respectively. Then the columns
of
![$A$](img8.gif)
generate the same lattice as those of
![$A'$](img76.gif)
, if and only if
![$B=B'$](img78.gif)
.
In other words, two lattices are equal if and only if their
respective matrices have the same Hermite normal form.
Proposition 4
(lattice canonical form)
Given a full-dimensional linear lattice
![$L$](img24.gif)
,
there exists a unique representation
![$(H,0)$](img79.gif)
of
![$L$](img24.gif)
(i.e.
![$L= \{ x~\vert~x=Hy,\ y \in Z^n \}$](img80.gif)
), such that
![$H$](img81.gif)
is in Hermite normal form.
Proposition 5
(affine lattice canonical form)
Given a full dimensional affine
lattice
![$L$](img24.gif)
,
there exists a unique representation
![$(H,h)$](img82.gif)
of
![$L$](img24.gif)
(i.e.
![$L= \{ x~\vert~x=Hy+h,\ y \in {\cal Z}^n \}$](img83.gif)
), such that
![$H$](img81.gif)
is
in Hermite normal form and
![$ 0\leq h_i <H_{ii}, \ 1\leq i \leq n$](img84.gif)
.
For instance, consider the following lattice
:
its unique
canonical form is
Polylib can also handle unions of (affine
integral full dimensionnal) lattices. This provides a set of
objects which is closed
under union, intersection, image by invertible integral functions
(see [NRi00]).
For instance, consider the following lattice
:
its unique normal form is
Next: Important functions in Lattice.c
Up: Lattices
Previous: Lattices
  Contents
Sorin Olaru
2002-04-24