saschatimme / cddlib Goto Github PK
View Code? Open in Web Editor NEWThis project forked from juliapolyhedra/cddlib
Fork of CDD to help writing the CDDLib.jl Julia wrapper
License: GNU General Public License v2.0
This project forked from juliapolyhedra/cddlib
Fork of CDD to help writing the CDDLib.jl Julia wrapper
License: GNU General Public License v2.0
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
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.