1. Dual Conversion versus CDD, 64-bit

We now compare the implementation of Chernikova algorithm for 64-bit in

, denoted C3DD64, and the C-implementation using the double description method of the CDD library for 64-bit, denoted CDD64. Here we ignore the fact that CDD64 uses C-built-in double floating point or GNU multi-precision rational library which are both faster than C3DD64's integer computation.

In 6_fig:SPEC95_dual_conversion_dimension_C3DD64_CDD64_100, the histogram shows only green zones which mean that CDD64 is always faster than C3DD64. In fact, CDD64 is faster in

percent of all tests. Finally, total run times accumulated for all tests are compared: we have CDD64 is faster than C3DD64 with a ratio of

, which means approximately

times faster, for the SPEC95 convex hull sampled database.

The histogram in 6_fig:PerfectClub_dual_conversion_dimension_C3DD64_CDD64_100, shows green zones indicating the cases where CDD64 is faster than C3DD64 and red zones corresponding to the opposite cases. They are well separated by the dimension

, from which a time-run-based heuristic can be constructed as follows: We use CDD64 for constraint systems with dimensions lower than

and C3DD64 for those with higher dimensions. We however notice that CDD64 is faster in

percent of all tests, thus this heuristic does not seem to be necessary according to the total run times accumulated. We have CDD64 is faster than C3DD64 with a ratio of

, which means approximately

times faster, for the PerfectClub convex hull sampled database.

**Figure 31:** PerfectClub: Dimension C3DD64 vs CDD64 in sampled database
$\begin{figure} \centering\epsfig {file=POLYBENCH_evaluations/PerfectClub_C3DD64_... ...TABASE_100/dimension_C3DD64_CDD64_crite.eps,height=5.9cm,width=14cm}\end{figure}$

**Figure 32:** SPEC95: Dimension C3DD64 vs CDD64 in sampled database
$\begin{figure} \centering\epsfig {file=POLYBENCH_evaluations/PerfectClub_C3DD64_... ...TABASE_100/dimension_C3DD64_CDD64_crite.eps,height=5.9cm,width=14cm}\end{figure}$

The conclusion for run times of these two algorithms is that CDD64 is faster than C3DD64, and we have a good example of a heuristics which can be based on the experimental results. If we do not consider the exception problem, we can obtain the parallel algorithm's performance with this heuristics that is much easier to implement.