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

[Roberto Bagnara]

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.
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.  Please, do not hesitate to ask if you need
further explanations.
Cheers,

     Roberto

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it