rcdd (C Double Description) package for R

University of Minnesota, Twin Cities     School of Statistics     Rweb

This web page provides an interface from the R statistical computing environment to the cddlib library writen by Komei Fukuda.

News

New! Now at version 1.1 (2008-04-12). Fixes major bug in linear programming code in version 1.0-1 and earlier (gave error when negative Lagrange multipler in correctly posed problem).

Now at CRAN.

• Version 1.1
  • fix major bug in lpdd function, which does exact linear programming. Now handles equality constraints correctly.
  • add linearity function, that does part of what the redundant function does. More efficient when only this part is wanted.
  • add qneg function (unary minus for GMP rationals) qabs function (absolute value for GMP rationals) qinv function (multiplicative inverse for GMP rationals)
• Version 1.0-1
  • changes to make it work on Windows.
• Version 1.0
  • upgraded from cddlib 0.94d to cddlib 0.94f, which fixes a bug in the lpcdd function.
• Version 0.10
  • added allface which produces list of faces from H-representation.
• Version 0.9
  • added redundant which eliminates redundant rows from H-representation or V-representation.
• Version 0.8
  • added lpcdd which does linear programming with exact GMP arithmetic.
• Version 0.7-1
  • added qsign and qmatmult to GMP arithmetic functions
  • fixed ANOTHER bug in the documentation for scdd (before 0.7 V-rep was correctly explained but H-rep was incorrectly explained, a sign mistake; in 0.7 H-rep was correct, but V-rep made incorrect, sign change applied to both was wrong, now both correct).
• Version 0.7
  • should build under windows and mac (GNU MP bignum library still needed).
  • fixed bug in documentation of scdd function.
  • copied cddlibman.pdf from cddlib distribution into doc folder
  • added qsum and qprod to GMP arithmetic functions
• Version 0.6-3
  • configure now checks for libraries.
• Version 0.6-2
  • Added package vignette.
  • changed LIBS to LDFLAGS following autoconf conventions.
  • in scdd H-representation now allowed to be matrix with zero rows.
  • fixed z2q so it preserves attributes (expecially "dim").
  • modified error messages as per Writing R Extensions, Sec 1.8.
• Version 0.6-1
  • Fixed a bug in subset functions.
  • Configuration now uses autoconf.
• Version 0.6
  • Added an example for the scdd function explaining one way to obtain convex hulls in spaces of arbitrary dimension.
  • Added more functions to do GMP rational arithmetic.
  • Added functions to produce the set of all faces from the incidence list. These are now obsolete. See the allfaces function added in version 0.10.

The package is installed on our Rweb server and can be tried out there.

If you don't know how to use Rweb, here is a web page with some Rweb examples for a paper.

Documentation

The package vignette has many examples of using the package.

The R help files (HTML version) for the package are the real documentation.

Start with the help for

• the scdd function, which converts between H-representation (solution set of linear equalities and inequalities) and V-representation (convex hull of points, rays, and lines) of convex polyhedra
• the lpcdd function, which does linear programming
• the redundant function, which removes redundant elements from H-representation or V-representation
• the allfaces function, which produces all nonempty faces of a convex polyhedron

All of these functions use either the usual computer floating point arithmetic (which causes problems because of inexactness) or exact infinite-precision rational arithmetic. Hence even the linear programming provided by the lpcdd function is unlike that done by other R packages.

Installation

To use the package you need to get and install

• the R statistical computing environment
• the GNU Multiple Precision arithmetic library
• the rcdd package

R statistical computing environment

Obtain from http://www.r-project.org/ or from one of the CRAN mirrors listed there. Either obtain and install binaries for your particular OS, or compile from source.

the GNU Multiple Precision arithmetic library

Obtain from http://gmplib.org/ or from your operating system vendor. This is a standard GNU package and comes with many Linux distributions and may be found at the web sites of other vendors that distribute free software.

The source code for the library is found at

http://gmplib.org/#DOWNLOAD

To satisfy the distribution requirements of the LGPL here is a copy of the source code for GMP version 4.2.2, but don't download it from here, go to gmplib.org to get the current version.

the cddlib library

This library (found at http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html), although it does all the real work for the rcdd package, is no longer required.

Due to difficulties in building cddlib, we have simply incorporated version 0.94d of it into the code of rcdd.

the rcdd package

If the GMP libraries are found in standard places, then either do in R

install.packages("rcdd")

or obtain right here (rcdd_1.1.tar.gz) and install from the unix command line as follows

R CMD INSTALL rcdd_1.1.tar.gz

Otherwise (if the GMP libraries are in a nonstandard place) something like

export CPPFLAGS="-I/APPS/include"
export LDFLAGS="-L/APPS/lib"
R CMD INSTALL rcdd_1.1.tar.gz

works, where /APPS/include is the directory where the include files for these libraries are found and /APPS/lib is the directory where the libraries themselves are found.

It seems that when the libraries are in /usr/local one still needs this

export CPPFLAGS="-I/usr/local/include"
export LDFLAGS="-L/usr/local/lib"
R CMD INSTALL rcdd_1.1.tar.gz