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.
Angela,
P M Hill wrote:
Angela,
--
On Mon, 11 Jun 2001, Angela Stazzone wrote:
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.
you mean its a hack ;) ssshhh - don't let Roberto hear.
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).
Ok.
Since minimize() is too expensive, in the PPL we use the flag
To expensive for what?
In time of computing.
If you only invoke it rarely, then the cost does not matter as much.
'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
Sounds loopy.
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.
I think you have - but that is not difficult.
My first thought is that none of this will be of any use unless this mimimize operator is idempotent. Otherwise, you may find the result of minimize is not (according to your above specification) minimized.
Seriously though, we must have a definition of what it is meant to do, otherwise, we cannot use minimize. Is minimize meant to provide a normal form?
ciao, Pat
The fact is that we want to check if, when the flag 'minimized' is set, the system is indeed minimized. Invoking minimize() (I think it should be idempotent) and checking if the resulting system is equal to the initial one is not efficient, while Gauss' elimination and back-substitution are less expensive in terms of efficiency.
Ciao, Ange.
PPL-devel mailing list PPL-devel@cs.unipr.it http://www.cs.unipr.it/mailman/listinfo/ppl-devel
[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.
Ciao Elisa
PPL-devel mailing list PPL-devel@cs.unipr.it http://www.cs.unipr.it/mailman/listinfo/ppl-devel
participants (3)
-
Angela Stazzone -
Elisa Ricci -
P M Hill