[PPL-devel] Re: Documentation

[P M Hill]

Hi,

Note that I still don't have Le Verge. So I can only comment on the
extracts included in the mail.

> P M Hill wrote:
> 
>  > Angela,
>  >
>  > Starting with page 180, the definition of redundant,
>  > I find this hard to follow.
>  > In the context of a polyhedra, we have already extreme rays
>  > and we know these are not redundant.
>  > (But a ray which is defined by just a point, is only unique up to a
>  > positive multiple.)
>  >
>  > Any other ray that is not extreme nor in the lineality space is redundant
>  > in the sense that it is the positive combination of extreme rays and
>  > lines.
> 
> The PPL is based on the double description of a Polyhedron and on the 
> Chernikova's algorithm for "finding an irredundant set of vertices and 
> rays of a given polyhedron defined by a mixed system of linear equations 
> and inequalities" (Le Verge - A note on Chernikova's algorithm - page 
> 1). Here does not appear any reference to extremal rays, but in the 
> recursive construction of the set of rays starting from inequalities I 
> found "The irredundant set Q' of extremal rays of the new cone ..." (Le 
> Verge - page 6).
> I think that you're right: an extremal ray is not redundant...but I 
> can't understand what Le Verge means talking about "irredundant set of 
> extremal rays".

The word "irredundant" is misleading.

What must be meant wrt an irredundant set of extreme rays is
that a set of extreme rays must not include the extreme rays r1 and r2
where r1 and r2 are positive multiples of the other.  ie there exists
\lambda_1 >0 and \lambda_2 >0 such that \lambda_1 r1 = r2 and
\lambda_2 r2 = r1.

Note that either r1 or r2 can be safely removed.
They are both extreme rays and one will "generate" the other.

> 
> Moreover Le Verge give the definition of redundant vector in a set Q 
> (page 4) but this seems to be definitions of extremal ray.
> Then on page 5 there are charaterizations of extremal ray not belonging 
> to the lin. space and irredundant vector belonging to a subset of a 
> polyhedral cone.

An extreme ray cannot be in the lin.space.

Consider the x and y axes as lines spanning the lin.space 
L = the xy plane
so that the space is generated by l1 = (0,1) and l2 = (1,0).
Which means that we have the rays (0,1), (0,-1), (1,0), (-1,0).
Now the lin.space is all points \mu_1 l1 + \mu_2 l2 for any rationals 
mu_1, \mu_2. Then (1,1) is in L as it is l1 + l2
However (0,1) = (1,1) + (-1,0) = 1*(1,1) + -1*(1,0)
So lines (1,1) and (1,0) also can generate the xy-plane
and the y axes defined by any (0,y) is not an extreme ray.
Similarly with any point in L.

So any point in the lin.space can be generated by 
any t linearly independent points where t is the dimension.
For example, (1,1), (1,0) can also generate L.

I have not seen page 5, I cannot comment on these
"characterisations...". 

>  Then, on page 6, we have: " [...] If the adjacency property is not
> taken into account, it can be shown that the resulting set Q'
> constains all extremal rays...this set is not irredundant in
> general...".

I assume here that irredundant means that one ray is not a 
positive combination of another.

> Well, I'm a bit confused! Can an extremal ray be redundant? And if
> it can, does exist a definition for this? I found only
> characterization.

 "Can an extremal ray be redundant?" I do not like the terminology
"redundant" here. It seems to indicate that if r1 = \lambda_2 r2 that
r2 is redundant. However, equally, as indicated above, r1 can be
safely removed and r2 kept.
So, both r1 and r2 are redundant.
If we removed all redundant extreme rays, we could have nothing left!

We have to talk about a set of extreme rays and instead of
"irredundant" I would prefer we said that the set of extreme rays was
`reduced': meaning that no ray in the set was a positive multiple of
any other ray in the set.

Similarly, we can say that the set of lines is "reduced" meaning that
it is a minimal spanning set of points for the space.

> 
> > > > [Angela]
> > > > In general we can say that a system of constraints is minimized if it
> > > > does not contain redundant constraints, but we want it also to be
> > > > normalized (the GCD of the coefficient must be 1).
> > > >
> 
> I think that a system of constraints is minimized if it is bilt by the
> least number of irredundant equalities and inequalities. This
> rapresentation can not be unique.
> 
> A system of generators is minimized if it is built by the least number
> of irredundant lines, rays and verteces (they are extreaml generators).
> This rapresentation is unique up to a positive coefficient if we are
> considering a pointed cone (i.e. the polyhedron is without lines).
> 
> I think that the test for checking if generators are really minimized
> must consider the previous consideration: we have to normalize before
> checking if the two systems of generator are equal.

I believe that we are confusing the declarative meaning of "minimised"
with the operational things that need to be done to 
a) check it is minimised and 
b) to convert a set to a minimised one.  
We also seem to be in doubt as to whether "miminised" means that we
have some canonical form for the set that is also minimised.

As I said above, I prefer to talk about a "reduced" set to mean that
we cannot remove any element from the set without altering the
polyhedra being generated.

Then, we can also see (if it is necessary) if we can convert such a
reduced set to a canonical reduced set that is unique for any given
polyhedra.  Generators in such a set would presumably have integer
coefficients for which the gcd = 1.

I see that we have three types of simplification/reduction
1 to take an arbitrary set of rays (and possibly a set of lines) 
  and reduce it to a set of extreme rays and a set of lines.
2 to take the result of 1 and find reduced sets of extreme rays and lines.
3 to take a reduced set as produced in 2 and normalise it to a provide
  unique form of reduced set.

The terminology "redundant, "irredundant", "minimise" seems to me to
confuse these different simplification steps.

ciao,
  Pat

--