third_party/cddlib/README

2012-04-30 (April 30, 2015)
-----------------------------------------------
C-Library cddlib (version 0.94h) README FILE
-----------------------------------------------
1. The C-library  cddlib is a C implementation of the Double Description 
Method of Motzkin et al. for generating all vertices (i.e. extreme points)
and extreme rays of a general convex polyhedron in R^d given by a system 
of linear inequalities:

   P = { x=(x1, ..., xd)^T :  b - A  x  >= 0 }

where  A  is a given m x d real matrix, b is a given m-vector 
and 0 is the m-vector of all zeros.

The program can be used for the reverse operation (i.e. convex hull
computation).  This means that  one can move back and forth between 
an inequality representation  and a generator (i.e. vertex and ray) 
representation of a polyhedron with cdd.  Also, cdd can solve a linear
programming problem, i.e. a problem of maximizing and minimizing 
a linear function over P.

The version 0.94 is the seventh release of libcdd. New functions
added in this release include dd_MatrixCanonicalize,
dd_FindRelativeInterior and dd_ExistsRestrictedFace.  These
functions are LP-based and should be reasonably efficient.
The sample programs such as redcheck.c, testlp1.c and allfaces.c
show how these functions can be used to remove redundancies,
to compute the dimension and all faces of an H-polyhedron.

In addition to the new functionalities, many small bugs have
been fixed.  For example, the mishandling of empty H-polyhedra
has been fixed for the representation conversion.

If you find some problems or bugs, please kindly report them to
fukuda@ifor.math.ethz.ch.  Please read README.whatsnew for the changes 
over the last release.

The documentation (cddlibman.tex) is still incomplete but contains 
descriptions of the most important functions. Please look at the examples,
testcdd*.c, testlp*.c, simplecdd.c, lcdd.c, redcheck,c for how 
the library functions can be used in user's C-codes.

2. One convenient feature of cddlib is the ability
to handle essentially any data.  More precisely, it can
generate an H-representation of a V-polyhedron which is not
full-dimensional, and it can generate a V-representation
of an H-polyhedron which has no extreme points.

3. A little caution is in order.  Many people have seen 
numerical problems when the floating version of cddlib
is used.   As we all know, floating-point computation
might not give a correct answer, especially when an input
data is very sensitive to a small perturbation.  When
some strange behavior is observed, it is always wise
to create a rational approximation of the input
(for example, one can replace 0.3333333 with 1/3)
and to compute it with cddlib compiled with gmp rational
to see what a correct behavior should be.  Whenever the time
is not important, it is safer to use gmp rational arithmetic.

If you need speedy computation with floating-point arithmetic, 
you might want to "play with" the constant "dd_almostzero" defined 
in cdd.h:

   #define dd_almostzero  1.0E-6

This number is used to recognize whether a number is zero: 
a number whose absolute value is smaller
than dd_almostzero is considered zero, and nonzero otherwise.
You might want to change this to modify the behavior of cddlib.
Another thing one can do is scaling.  If the values in one column of
an input is of smaller magnitude than those in another column, 
scale one so that they become comparable.

4. The cddlib package is in "tar"ed and "gzip"ed format with name
cddlib-***.tar.gz, where *** is the version number.  The standard
download site for the package is

     web site : http://www.ifor.math.ethz.ch/~fukuda/cdd_home/index.html
     file name: cddlib-***.tar.gz

In order to unpack the package in a standard unix environment, type 
   
     % tar xvfz cddlib-***.tar.gz

where *** must be replaced by the appropriate version number, and
% is a unix prompt. 

For compilation of libcdd, go to the cddlib top directorycddlib
and follow the general instruction of autoconf.  In generic
unix/linux environment, use "./configure" and "make".
To enforce a certain compiler to be used, specify it as

   CXX=g++ ./configure

The default compiler is gcc.
Note that one must install GMP-4.* (or higher) first.

For compilation of MathLink programs,
you need a binary "mprep", MathLink library "libML.a" and include file
"mathlink.h" which come with Mathematica.   I have tested for Mathematica 4.1
and 3.* on MacOSX and Linux.  This part is not "autoconf"igured
and thus one needs to edit Makefile in the src-mathlink and src-mathlink2 subdirectories. 

To install the library in public directory of unix environment, 
just type "make install".  The default installation directory
is /usr/local.  If you want to select other places, use
"./configure --prefix=<DIRNAME>" to configure with your favorite
<DIRNAME>. 

One might have to make the files publicly readable by chmod.
Once the files are properly installed, any user can use compile
one's own code (e.g. testcdd1.c) and link it with libcdd by
  
   % gcc -I/usr/local/include -L/usr/local/lib testcdd1.c -lcdd

or (with GMP rational arithmetic)

   % gcc -I/usr/local/include -L/usr/local/lib -DGMPRATIONAL testcdd1.c -lcddgmp -lgmp


5. cddlib comes with a MathLink version of cddlib that can be
called from Mathematica (tested for Mathematica 2.2, 3.0, 4.1, 5.1).
A few Mathematica notebooks are included to explain how one can 
use this program "cddmathlink" from Mathematica
to manipulate polytopes.  Please check the files, 
cddml-notbook.ma, cddml-PolytopeSkeleton.ma, cddml-DietProblem.ma,
and cddml-Zonotope.ma, in the mma subdirectory.  I could 
compile cddmathlink.c for Macintosh and Windows.  Please use
gcc instead of g++ to compile cddlib.  I have put 
binaries for different platforms in 
http://www.cs.mcgill.ca/~fukuda/download/cdd/cddlibml_binary/  .


6. The library cddlib is free software, but if cddlib turns out to be useful, 
please kindly send me (at the address below) a note or a paper mentioning 
what purpose and how cdd has been used for. The most powerful support 
for free software development is user's appreciation.   

For more information, contact

Komei Fukuda <fukuda@math.ethz.ch>
Institute of Theoretical Computer Science
ETH Zentrum, CH-8092 Zurich, Switzerland
Tel +41-1-632-4023, Fax +41-1-632-1063
http://www.ifor.math.ethz.ch/staff/fukuda/

// END of README