previous_group previous up next next_group
Previous: 2. Projection Up: 2. Large Operands Next: 3. Related Work

3. Convex Hull

As mentioned above, the program ocean.f in the benchmark PerfectClub is a special case, which PIPS has difficulty to deal with. The first phenomenon is observed by the very expensive computation of convex hull operator in PIPS for the two constraint systems in 6_fig:example_convex_hull_two_large_constraint_systems.

Figure 6: Example: first fragments of two large constraint systems which fail the convex hull operator
\begin{figure}
\begin{verbatim}...

The number of generating vertices grows exponentially with the number of constraints just as for an hypercube. The implementation of Chernikova algorithm available in POLYLIB and used in $C^3$ cannot handle the dual conversion of the first constraint system, thus an exception ``out of table space'' is detected. Even after the partial factorization by Corinne ANCOURT and Fabien COELHO, the polyhedra remains too large.



Nguyen Que Duong
2006-09-16