1. $C^3$ approach: Constraints versus Generators, 64-bit

In this section, we compare the 64-bit implementation that manipulates directly on constraint systems, i.e., the Fourier-Motzkin elimination method, denoted P64, and the implementation using the double description method for 64-bit, denoted PDD64, which projects the polyhedron by converting its constraint system to a generating system and then does the projection using this representation . The first one was already available in $C^3$, and the second one was implemented by me, in order to evaluate the two approaches.

Our comparisons only make sense when we have in hand the constraint systems but not their corresponding generating systems at the same time. This is normally the case in $C^3$ library. For New POLKA library, the generating system of a polyhedron can be present or not, depending on the context. POLYLIB library always keep the two representations of the polyhedron in question, thus our comparison does not make sense except the fact that we can check the equivalence of the outputs of different implementations.

The polyhedral databases used here are the projection sampled databases (see 6_subsec:polyhedral_databases). In 6_fig:PerfectClub_projection_dimension_P64_PDD64_100, the histogram legend shows three colors red, blue and green. However, in this case, we only have the red zones which present the cases where constraint manipulation P64 is faster than the double description method PDD64 .

This histogram has two axes representing the number of variables in constraint systems and the number of constraint systems available in PerfectClub polyhedral sampled database for the projection operator. We can see this information in the first line of the figure header, as well the percentages: P64 is faster in all tests, PDD64 is never faster.

Furthermore, total accumulated run times of all tests are compared, from which the global acceleration is derived and displayed in the second line of figure header: the total run time of PDD64 divided by the total run time of P64 which shows that P64 is approximately $1253$ times faster than PDD64.

Figure 25: PerfectClub: Dimension P64 vs PDD64 in sampled database

As for satisfiability test in 6_sec:satisfiability_results, histograms with dimension axis are more informative than the others.

The conclusion about the run times of two algorithms is P64 is much faster than PDD64, for PerfectClub sampled databases: $450$ times faster. The same results are seen for SPEC95 databases, but not displayed here.

The big difference in performance of P64 and PDD64 suggests that in case of performance problems for Double-Description-method-based libraries such as New POLKA and PPL , implementations using Fourier-Motzkin elimination method might be a solution.