June 2001 - PPL-devel - BUGSENG Mailman

Polyhedra/src Polyhedron.cc
by Angela Stazzone 13 Jun '01

13 Jun '01

CVSROOT: /usr/local/cvsroot/pma2000 Module name: Polyhedra Changes by: stazzone(a)sandbox.cs.unipr.it 01/06/13 17:25:26 Modified files: src : Polyhedron.cc Log message: Removed some redundant descriptions. Removed some useless \fn and \param Doxygen directives. Maybe found a couple of bug (will fix them tomorrow). Others little changes in documentations. In description of OK() we refer to homogeneization (then to positivity constraint and vertex needed): should users know about it?

1 0

Polyhedra/src Polyhedron.inlines.hh
by Angela Stazzone 13 Jun '01

13 Jun '01

CVSROOT: /usr/local/cvsroot/pma2000 Module name: Polyhedra Changes by: stazzone(a)sandbox.cs.unipr.it 01/06/13 16:55:42 Modified files: src : Polyhedron.inlines.hh Log message: Removed some \fn and \param Doxygen directives. Removed some useless descriptions. Other little changes in comments.

1 0

Polyhedra/src interface.cc
by Roberto Bagnara 13 Jun '01

13 Jun '01

CVSROOT: /usr/local/cvsroot/pma2000 Module name: Polyhedra Changes by: roberto(a)sandbox.cs.unipr.it 01/06/13 16:29:01 Modified files: src : interface.cc Log message: I just made some experiment: please ignore.

1 0

Polyhedra/src Polyhedron.defs.hh
by Angela Stazzone 13 Jun '01

13 Jun '01

CVSROOT: /usr/local/cvsroot/pma2000 Module name: Polyhedra Changes by: stazzone(a)sandbox.cs.unipr.it 01/06/13 16:27:12 Modified files: src : Polyhedron.defs.hh Log message: Minor changes in comments.

1 0

Polyhedra/src GenSys.cc GenSys.inlines.hh
by Angela Stazzone 13 Jun '01

13 Jun '01

CVSROOT: /usr/local/cvsroot/pma2000 Module name: Polyhedra Changes by: stazzone(a)sandbox.cs.unipr.it 01/06/13 12:09:42 Modified files: src : GenSys.cc GenSys.inlines.hh Log message: Fixed some FIXME (!) Added comments in generators_satisfy_constraint().

1 0

Re: [PPL-devel] Re: Documentation
by Angela Stazzone 13 Jun '01

13 Jun '01

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". 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. 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...". 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. Ciao, Angela.

2 1

Polyhedra/src Polyhedron.cc
by Elisa Ricci 12 Jun '01

12 Jun '01

CVSROOT: /usr/local/cvsroot/pma2000 Module name: Polyhedra Changes by: ericci(a)sandbox.cs.unipr.it 01/06/12 12:28:11 Modified files: src : Polyhedron.cc Log message: Little changes in Polyhedron::OK() in the part of generator_are_minimize: we must normalize before checking if the two matrices are equal. The part added is preceded by #ifndef LASA.

1 0

minimize
by Angela Stazzone 12 Jun '01

12 Jun '01

Pat, the definition of minimized system is not yet very clear. At the moment we assume that the definition is given by the code of minimize() because we have no clear ideas on what we really need. 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). Since minimize() is too expensive, in the PPL we use the flag 'minimized' and we want that when it is set, the system is minimized in the sense that we can avoid to invoke minimize(). To check if this flag is handled, we use OK(): it takes a system, makes a copy and calls minimize, then compare it with the system having flag minimized set, after invoking gauss(), backsubstitute(), sorting and normalizing it. If the two system are equal, it means that the flag is correctly handled and when it is set the matrix is minimized. I hope I'm not make you confused. Ciao, Angela.

3 3

Re: Documentation
by Angela Stazzone 11 Jun '01

11 Jun '01

Angela Stazzone wrote: > Pat, > the .pdf attached here is the latest version of the developers reference > manual. The original message have not been sent because it was too big (sorry!), but now you can find the documentation online. > There are still something not clear. > I tried to give redundancy definition independently from saturation rule > and independence rule. I found the definition for equalities in G. B > Dantzig - Linear programming and extensions - Princeton University > Press, New Jersey 1963 pages 71 and I tried to give a meaningful > definitions for inequalities, lines, vertices and rays: can you check > them? > > The page documentation starts on page 178: can you give a look and let > me know if I used some notion before define it? > > Thanks, > Angela. > > ------------------------------------------------------------------------ > Name: devref.pdf > devref.pdf Type: Portable Document Format (application/pdf) > Encoding: base64

2 1

Polyhedra/src Matrix.cc Matrix.defs.hh Matrix. ...
by Angela Stazzone 11 Jun '01

11 Jun '01

CVSROOT: /usr/local/cvsroot/pma2000 Module name: Polyhedra Changes by: stazzone(a)sandbox.cs.unipr.it 01/06/11 17:59:27 Modified files: src : Matrix.cc Matrix.defs.hh Matrix.inlines.hh Log message: Comments rechecked: deleted some useless doxygen \fn directives.

1 0