[PPL-devel] Complexity of remove_dimensions

[Mario Mendez]

Roberto Bagnara wrote:
> Mario Mendez wrote:
> 
>> Hi again,
>>
>> I'm wondering what is the complexity (worst case, O(f(x,y)) for the 
>> 'remove_dimensions' method offered in the library. I checked the 
>> source code but it is kind of difficult to me to figure out the exact 
>> function.
> 
> 
> Dear Mario,
> 
> the worst case, time and space complexity of 'remove_space_dimensions'
> (please note the 'space' between 'remove' and 'dimensions') is
> exponential in the number of space dimensions of the original
> polyhedron.  This answer is not very precise, but is good enough
> for most practical purposes.  Please let us know if this is good
> enough for your purposes.
> 

More than enough, thanks


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


>> Thank you!
> 
> 
> It's a pleasure Mario.  You can also help us make the PPL better.
> For instance, Manuel Hermenegildo mentioned that someone (perhaps
> you?) found inaccuracies in our installation instructions for the
> Ciao Prolog interface of the PPL.  Is this correct?  If so, could
> you let us know so that we can improve the documentation?
> Did you have to patch the code too?  If so, can you let us have
> the details?

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.

> 
> 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).



> Many thanks in advance,
> 
>     Roberto
>