[PPL-devel] integer versus rational solutions

[Konrad Trifunovic]

Hi all,

here I attach an polyhedron of smaller dimensionality:
I also ask for 'contains_integer_point'. It does not give me
any result in reasonable time (actually I did not wait
until it gives any result, since it took more than few minutes).
I try it on 32-bit machine.

Thanks,
Konrad




2009/7/9 Konrad Trifunovic <konrad.trifunovic at gmail.com>:
> Hi,
>
> that's a good point.
> We DO NOT need NNC polyhedra. Closed Polyhedra are fine
> (at least for dependence analysis). Do You think that using
> C_Polyhedron would help us avoid the much of the complexity problems?
>
> from my analysis (by looking at the PPL code) I have seen
> that the "contains_integer_point" methods call the MIP
> (Mixed Integer Programming) routines, to solve the system of constraints.
> I have seen that it behaves differently in the case of Convex and
> NNC polyhedra.
>
> regards,
> Konrad
>
> 2009/7/9 Roberto Bagnara <bagnara at cs.unipr.it>:
>>
>> Konrad Trifunovic wrote:
>>> I attach a patch that uses 'integer existence test'.
>>> I have forced the use of dependence check.
>>
>> Hi there.
>>
>> I am sorry if the answer is obvious, but I am wondering
>> why you are using NNC polyhedra (NNC_Polyhedron) instead
>> of ordinary polyhedra (C_Polyhedron).  Do you need to
>> characterize rational solutions and use strict constraints?
>> 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
>>
>> --~--~---------~--~----~------------~-------~--~----~
>> You received this message because you are subscribed to the Google Groups "GCC GRAPHITE" group.
>> To post to this group, send email to gcc-graphite at googlegroups.com
>> To unsubscribe from this group, send email to gcc-graphite+unsubscribe at googlegroups.com
>> For more options, visit this group at http://groups.google.de/group/gcc-graphite?hl=en
>> -~----------~----~----~----~------~----~------~--~---
>>
>>
>
-------------- next part --------------
  6 6
      0   8192      1   -8192     -1      0  
      1      0      0      0      1      0  
      1      0     -1      0      0   8191  
      1      0      1      0     -1     -1  
      1      0     -1   8192      1      0  
      1      0      0     -1      0   8191  
-------------- next part --------------
size 1
space_dim 4
space_dim 4
-ZE -EM  -CM -GM  -CS +GS  -CP -GP  -SC -SG 
con_sys (not_up-to-date)
topology NOT_NECESSARILY_CLOSED
21 x 20 (not_sorted)
index_first_pending 21
0 0 0 0 0 0 8192 0 1 0 0 0 0 0 0 0 0 0 -1 0 =
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 =
0 0 0 0 0 0 8192 0 1 0 0 0 0 0 0 0 -1 0 0 0 =
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 =
0 0 0 0 1 0 -8192 0 -1 0 0 8192 0 0 0 0 0 0 0 0 =
0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 =
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 =
0 0 0 0 0 0 8192 0 1 0 0 -8192 0 -1 0 0 0 0 0 0 =
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 =
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 =
0 0 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 =
0 1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 =
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 =
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 =
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 =
0 0 0 0 0 0 -1 0 0 0 0 1 0 0 0 0 0 0 0 -1 >
0 0 0 0 0 0 8192 0 1 0 0 -8192 0 0 0 0 0 0 0 0 >=
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 >=
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 >=
8191 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 >=
8191 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 >=
gen_sys (up-to-date)
topology NOT_NECESSARILY_CLOSED
8 x 6 (not_sorted)
index_first_pending 8
1 0 0 0 0 0 C
1 8191 0 8191 0 0 C
1 8191 8191 8191 8191 0 C
1 0 8191 0 8191 0 C
8192 0 67100672 8191 0 8191 P
8192 0 67100672 8191 0 0 C
8192 67092481 67100672 67100672 0 8191 P
8192 67092481 67100672 67100672 0 0 C
sat_c
8 x 21
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 
sat_g
3 x 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0