Here we report a computational comparison of the LP algorithm and LP+Clarkson algorithm for higher dimensions (27 and 35). The instances we use below for the comparison are produced by Mathieu Dutour Sikirić who used redundancy removal for the study of Voronoi polytopes and C-type domain theory.
All input data files can be found in CtypeData . See Instructions for doing the experiments by yourself.
Remark that with floating-point arithmetic, the computation may not produce the correct result (numerical failure), and furthermore, the numerical irregularities may yield segmentation faults.
| d | n | Float | Exact (Rational) | |||||
|---|---|---|---|---|---|---|---|---|
| LP algorithm | LP+Clarkson | Speedup | LP algorithm | LP+Clarkson | Speedup | |||
| CTYPE 7 | ||||||||
| ctype7_0 (1%ess) | 27 | 2898 | 52s | 0.66s | 79 | 212s | 12s | 18 |
| ctype7_1 (1%ess) | 27 | 2898 | 120s | 0.68s | 176 | 168s | 9s | 19 |
| ctype7_2 (1%ess) | 27 | 2898 | 106s | 0.8s | 133 | 211s | 12s | 18 |
| ctype7_3 (1%ess) | 27 | 2898 | 126s | 0.69s | 183 | 174s | 9s | 19 |
| ctype7_4 (1%ess) | 27 | 2898 | 144s | 0.66s | 218 | 194s | 11s | 18 |
| ctype7_5 (1%ess) | 27 | 2898 | (numerical failure) | 0.7s | * | 294s | 18s | 16 |
| ctype7_6 (1%ess) | 27 | 2898 | 117s | 0.6s | 195 | 393s | 9s | 44 |
| CTYPE 8 | ||||||||
| ctype8_0 (0.4%ess) | 35 | 9075 | (seg. fault) | (seg. fault) | * | 103841s | 172 s | 604 |