[PPL-devel] Complexity of remove_dimensions

[Mario Mendez]

Roberto Bagnara wrote:
> 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?


No, it doesn't work that way, I just checked it again. If it helps, my 
Linux is Fedora Core 2

> 
>>> 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?

Yep, is an internal version synchronized by Subversion; I ran the 'make 
check' and takes a while ;-) but it worked. The only problem is that my 
computer crashed shortly after the message '512 tests passed' so all the 
huge temporary files (tests/BD_Shape, tests/Polyhedron were deleted by hand!


> All the best,
> 
>    Roberto
>