previous_group previous up next next_group
Previous: 5. Parallel Algorithm: Up: 3. Results for Satisfiability Next: 6. Arithmetic Precision: 64-bit


5. Integer versus Rational: 64-bit

In above comparisons, we have ignored a fact that algorithms implemented for the satisfiability test can be integer or rational. The integer algorithm tests if the constraint system contains integer points or not, whereas the rational tests if the constraint system contains rational points or not. The algorithm implemented in JANUS is integer where $C^3$ Simplex and Double Description method are rational. $C^3$ Fourier-Motzkin is a rational algorithm with an add-on test that in some cases can verify if the solution are rational or integer. Thus, it is in fact an integer/rational algorithm. In our context, integer answer means more precision than rational one, therefore in this section we compare the differences between results of those algorithms.


Table 11: PerfectClub: Numbers of not precise results in sampled database
  PerfectClub
integer vs rational declared feasible #operations
JANUS 64-bit 0 12668
$C^3$ Simplex 64-bit 5 12668
$C^3$ Fourier-Motzkin 1 12668
$C^3$ Double Description method 8 12668



Table 12: SPEC95: Numbers of not precise results in sampled database
  SPEC95
integer vs rational declared feasible #operations
JANUS 64-bit 0 16303
$C^3$ Simplex 64-bit 4 16303
$C^3$ Fourier-Motzkin 0 16303
$C^3$ Double Description method 3 16303


6_tab:PerfectClub_satisfiability_integer_rational_100 and 6_tab:SPEC95_satisfiability_integer_rational_100 show numbers of cases where $C^3$ Simplex, Fourier-Motzkin and Double Description method give the answer $not empty$ while the constraint system contains no integer point but only rational points, with sampled databases [*]. We can see that the percentage of not precise results is rather small. This suggests that the difference is not significant.


previous_group previous up next next_group
Previous: 5. Parallel Algorithm: Up: 3. Results for Satisfiability Next: 6. Arithmetic Precision: 64-bit
Nguyen Que Duong
2006-09-16