This repository has been archived by the owner on Jun 11, 2018. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 3
/
README
149 lines (115 loc) · 6.23 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
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
[email protected]. 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 <[email protected]>
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