[PPL-devel] minimize

[Angela Stazzone]

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 at cs.unipr.it
> http://www.cs.unipr.it/mailman/listinfo/ppl-devel