third_party/cddlib/README - RealtimeRoboticsGroup/test - Gitiles

 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
	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