[PPL-devel] integer versus rational solutions

[Michael Claßen]

On Mon, Jul 13, 2009 at 3:27 PM, Roberto Bagnara<bagnara at cs.unipr.it> wrote:
> Michael Claßen wrote:
>>
>> On Mon, Jul 13, 2009 at 1:11 PM, Tobias
>> Grosser<grosser at fim.uni-passau.de> wrote:
>>
>>> If I got your comments right, you warned that adding large constants
>>> like MAX_INT might be bad for compile time performance. That is
>>> something I did not understand and as adding the constraint to the
>>> context improves the code generated by CLooG, I would like to keep
>>> adding these constraints as long as compile time allows.
>>
>> from my experience, large constants can influence the complexity of
>> many algorithms (e.g. Fourier-Motzkin) in the polytope model, because
>> of the simple fact that at some points, the algorithm has to compute
>> the lowest common denominator (LCD) of entries in matrices. Now, if
>> you combine that with the fact that sometimes you have expressions
>> like "constant-1" or "constant+1", those LCDs can get extremely big,
>> which makes the usage of GMP almost unavoidable and slows down
>> computation a lot. It also might increase memory usage too.
>>
>> Also, larger constants create more cases where inequalities are not
>> redundant, whereas small constants like 0, 1, 2 often create cases
>> that can be simply ignored because they are already expressed by other
>> inequalities.
>>
>> I hope I haven't missed the point here, but this is just how I have
>> experienced the problem so far when working with FM and other
>> algorithms on polytopes containing large constants (as they often
>> result from using our tiling technique in LooPo).
>>
>> If anyone has any approach to how to deal with this specific problem,
>> I would be very interested to hear about it!
>
> Is approximation acceptable in your application?  There are techniques
> to compute an upward approximation of a given polyhedron (i.e., a
> polyhedron containing the given one) so as to limit the number of
> bits of the coefficients.
>
> The idea, due to Goran Frehse, is the following: for each constraint
> do:
>
> 0) start, e.g., with
>
>     109*x + 121*y <= 100;
>
> 1) truncate homogeneous coefficients to, e.g.,
>   3 bits, obtaining
>
>       6*x +   6*y <= ?;
>
> 2) solve an LP problem to push out the plane, obtaining:
>
>       6*x +   6*y <= 600/109;
>
> 3) approximate the inhomogeneous coefficient to next integer,
>   obtaining
>
>       6*x +   6*y <= 6.
>
> So the cost is one LP problem per constraint.  Whether
> it is worthwhile or not depends on the application.
>
> With Goran we have a plan to implement this and other techniques
> in the PPL.  If this may be useful to you, we may increase the
> priority of the job.
> Cheers,
>
>   Roberto

Hello Roberto,

thanks for the clarification. But unfortunately, I need a precise
solution, not an approximization. I use the exact number of points in
those sets to calculate the position in a buffer.

It might be possible to use a less precise heuristic, but the
heuristic would have to satisfy some properties:

1) it should be deterministic, I always have to know where an element
is placed inside the buffer
2) if there are two polyhedrons of different size, the heuristic
should yield an approximization that is also different in size for the
two polyhedrons. This is necessary, because I count the number of
elements in the resulting polyhedron in order to compute a buffer
location. And this buffer access function has to be injective (but not
necessarily bijective!).

I think 1) should be given relatively easily, Unfortunately, I think
2) is probably impossible to guarantee using the above heuristic.

I have to say that it puzzles me that there seems to be so little
demand for a precise way of dealing with something like Z-polytopes. I
have met a number of people already who are looking for the same thing
as I am, but apparently, they are either not complaining or just not
aware of this discussion.

Thanks for the efforts anyway, I really appreciate this discussion!

regards,
Michael