[PPL-devel] [Fwd: Projection in the PPL]

[Axel Simon]

On Wed, Oct 15, 2003 at 11:12:38AM +0200, Roberto Bagnara wrote:
> Roberto Bagnara wrote:
> >I always thought that projection of polyhedra is done via Fourier Motzkin
> >elimination. Is that true for the PPL library as well or is there a way to
> >reformulate the projection operation on the generator set?
> 
> Hello Axel,
> 
> No, the PPL does not use Fourier-Motzkin elimination for projection.
> And yes, it does define projection on the system of generators of
> the polyhedron.  If the polyhedron happens to have such a system
> of generators up-to-date (as is the case, for instance, after
> a poly-hull operation), projection can be done much, much more
> efficiently that way than by using Fourier-Motzkin elimination.

Projection can increase the size of polyhedron if it is represented by a 
set of halfspaces. Can the size of a polyhedron represented by its 
generators increase as well?

> Experimentations conducted with the cTI system
> (http://www.cs.unipr.it/cTI/) showed speedups of up to two orders
> of magnitude that were essentially due to the increased efficiency
> of the projection operation.  Details about the algorithms we employ
> are in the PPL code.

Interesting. I looked at the code weeks ago and I figured that the only 
thing you do is removing the rows of those variables which should be 
projected out. Is that it? Is it that easy?!

Thanks,
Axel.