How To Run Clarkson's Algorithm Experiments

Here are the steps to perform the experiment of comparing the naive LP algorithm and Clarkson's algorithm.

1. First you have to compile the cddlib library cddlib-0.94m. The source can be obtained from GitHub site. To compile cddlib correctly, you need to preinstall GNU gmp library at a standard location such as /usr/local. Needless to say, you need a modern C compiler.
2. After you compiled cddlib-0.94m successfully, you must move to "src" subdirectory. Copy all the input files, ucube*.ine and ducube*.ine, to this subdirectory.
3. Then, execute commands in terminal such as
   ./redundancies ducube10k_4d.ine > ducube10k_4d_float.out
   ./redundancies_gmp ducube10k_4d.ine > ducube10k_4d_gmp.out
   ./redundancies_clarkson ducube10k_4d.ine > ducube10k_4d_c_float.out
   ./redundancies_clarkson_gmp ducube10k_4d.ine > ducube10k_4d_c_gmp.out

   Above, ./redundancies executes the standard (naive) LP algorithm in float and ./redundancies_gmp the same algorithm in exact (GMP rational) arithmetic. ./redundancies_clarkson executes the LP+Clarkson algorithm in float and ./redundancies_clarkson_gmp the same algorithm in exact (GMP rational) arithmetic.

Note that the actual problems solved above are the dual problem. The ucube*.ine files represent H-representations of the polar of the convex hull of random points in hypercubes. The outcome of redundancies stays identical.

The current implementation of Clarkson's algorithm, redundancies_clarkson.c, works only for full-dimensional H-representations.

back