[PPL-devel] Complexity of remove_dimensions

[Roberto Bagnara]

Mario Mendez wrote:
>>> Another question: is there any "standard" algorithm to project a 
>>> system of linear (in)equations on certain dimensions, in the same way 
>>> 'remove_dimensions' is doing? If so, what is its name?
>>
>>
>>
>> Ehm, Mario, where is the camera?  Come on, I just know this has
>> got to be "Candid camera"!   :-D
>>
>> This is the third time you ask the same question:
>>
>>   http://www.cs.unipr.it/pipermail/ppl-devel/2005-July/006205.html
>>   http://www.cs.unipr.it/pipermail/ppl-devel/2005-July/006263.html
>>
>> Its name (please write it down _now_ :-) is 'map_space_dimensions'.
>> If you think 'map_space_dimension' is not what you need, if by
>> `"standard" algorithm' you meant something different, then (quoting
>> what I wrote in 
>> http://www.cs.unipr.it/pipermail/ppl-devel/2005-July/006205.html):
>> "Please, come back to us with a clearer explanation of what you have,
>> what you do and what you want, so that we can see what is your best
>> option."
>>
> 
> Actually, we are in the second case. I'm asking whether the algorithm 
> used in 'remove_dimensions' has an standard name (in Math literature) so 
> I can google for it to get more information, in the same way the 
> algorithm to solve a system of lin.eq. is called 'Gaussian elimination', 
> for instance.

Dear Mario,

I think the confusion comes from the fact that you did not reply to
my previous messages: since the clearer explanation of what you
wanted never arrived, I though you were asking the same thing.
Anyway, the algorithm we use for 'remove_space_dimensions'
consists in updating, if necessary, the generator representation
of the polyhedron and then in a simple filtering of the generators.
The algorithm used for the conversion is, as explained in the library's
documentation and web pages, an algorithm that was originally proposed
by T. S. Motzkin et al. [MRTT53], then rediscovered by N. V. Chernikova
[Che65], improved by H. Le Verge [Ver92], further improved by D. K. Wilde
[Wil93], K. Fukuda and A. Prodon [FP96], N. Halbwachs, Y.-E. Proy and
P. Roumanoff [HPR97], and B. Jeannet.
If you go to http://www.cs.unipr.it/ppl/details, the hyperlinks
will bring you to the relevant literature.

Notice that the algorithm we use is not the one (more widely known
but inadequate for our purposes) called "Fourier-Motzkin elimination".

> The only problem I found is that the instructions do not mention the 
> (required)
> 
> /sbin/ldconfig
> 
> command necessary to update the system in order to 'accept' PPL.

Well, this is a system-dependent thing and, moreover, something that
ordinary user cannot do.  Couldn't you simply define LD_LIBRARY_PATH?

>> Another thing we would like to know are the versions of Ciao Prolog
>> and of the PPL you are using and whether you have experienced the
>> problem described in
>>
>>   http://www.cs.unipr.it/pipermail/ppl-devel/2004-October/004971.html
>>
>> If so, do you know if a cure is available?
> 
> 
> I did not experienced that problem. I'm using PPL 0.7 + SVN Ciao 
> (therefore, no particular release of Ciao).

I assume SVN stands for Subversion, right?  In other words is
a version for internal use only: is that correct?
Can you please confirm that PPL 0.7 passes `make check' on
your installation?
All the best,

    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