Michael Claßen wrote:
On Mon, Jul 13, 2009 at 1:11 PM, Tobias Grossergrosser@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