[PPL-devel] integer versus rational solutions

[Michael Claßen]

Hello,

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!

greetings,
Michael