9
$\begingroup$

My work requires me to enumerate all vertices of a polytope defined by linear inequalities from time to time. And I'm mainly working with _Mathematica 9.0 on Mac OS X 10.9. So I wonder are there any packages in Mathematica which can be used for vertex enumeration.

I know a very old Mathematica package VertexEnum.m which can be found from here.

I have tested the package and it still works on Mathematica 9.0 with a minor modification. The main drawback of this package is its efficiency. It's much slower than calling MPT3 toolbox in MATLAB via MATLink package on Mathematica. As far as I know, they share the same vertex enumeration algorithm, the Double Description Method of Motzkin et al..

Currently I have several questions in mind. I tried to Google them but I failed to get answers. Any comments or suggestions are most welcome.

  1. Are there any packages in Mathematica doing vertex enumeration on _Mathematica?
  2. Is there a latest VertexEnum.m package whose efficiency is increased?
  3. Is there a Mathematica interface to cddlib which works with Mathematica 9.0 on Mac OS X 10.9?

As I don't have enough reputations to post too many links. Interested readers can go to comments for more information.

$\endgroup$
  • 1
    $\begingroup$ The C-library cddlib is a C implementation of the Double Description Method of Motzkin et al. which is widely used for vertex enumeration. One can find the homepage of cddlib here. The author of cddlib happens to be the same person with the author of VertexEnum.m package, Prof. Komei Fukuda. Maybe he wants to make the algorithm compatible with more platform, so he stops updating VertexEnum.m and concentrates on cddlib. $\endgroup$ – Han Xiao Sep 14 '14 at 6:52
  • $\begingroup$ In his homepage, he provides an Mathematica interface to cddlib. However, it's platform dependent and too old to work with current version of Mathematica. I tried to recompile the Mathematica interface to cddlib, but I got stuck at the very beginning. Actually, I have another question on recompiling Mathematica interface to cddlib. Interested readers can find the question here. $\endgroup$ – Han Xiao Sep 14 '14 at 7:05
  • 1
    $\begingroup$ Under Linux I had no problems to compile the cddmathlink,cddmathlink2 and cddmathlink2gmp libraries for cddlib-094g using the following complier flags MLFLAGS = -lML64i4 -lpthread -lrt -luuid -ldl for Mathematica 10. They work perfectly. Write me an e-mail if I should send you the Makefile. $\endgroup$ – Holger I. Meinhardt Dec 7 '14 at 16:10
4
$\begingroup$

Instead of using cddlib you can use the nicely packaged version in polymake, which certainly installs without problems on OS X, and you can just call by an external function call from Mathematica (no mathlink interface necessary). polymake has a lot of other functionality too.

$\endgroup$
  • $\begingroup$ Thank you for sharing. Polymake satisfies all my requirements. Besides, I found another open-source software called Sage which is incredibly powerful. With all the respect, let us just leave this question open for now and see where it goes. $\endgroup$ – Han Xiao Sep 15 '14 at 8:11
  • $\begingroup$ Thank you so much for your answer. I didn't realize the usage of Polymake until recently. But I have difficulty in calling external functions from Mathematica. Hence a new question is created. I referred to some tutorials on external calls. But I still have no idea on how to call functions in Polymake. So can you share your ideas on calling functions in Polymake from Mathematica? $\endgroup$ – Han Xiao Apr 4 '16 at 6:32
3
$\begingroup$

Glancing through your last posts, it seems to me that you are still looking for a library under Mathematica that enumerates all vertices of a polytope. But you are very close to the answer. It is the C-implementation of the cddlib library for Mathematica by Komei Fukuda. This also works fine under Mathematica. There, the library is called Cddmathlink and you have to compile it by yourself. Under Linux (SLES11) I have to impose the following compiler flags

MLFLAGS = -lML64i4 -lpthread -lrt -luuid -ldl

to successfully compile cddmathlink, cddmathlink2gmp and cddmathlink2 under Mathematica 10.x (see also my comment from Dec. 7 2014 above). However, you have to download cddlib-094f.tar.gz and cddlib-094h.tar.gz. The former you use to copy the directories src-mathlink and src-mathlink2 in the root directory of cddlib-094h. Edit the Makefiles in src-mathlink and src-mathlink2 folders, and then call the commands "./configure && make all" in the root directory of cddlib-094h. After the compilation has terminated successful, you need to change in src-mathlink and src-mathlink2 to call again the make command.

I use these libraries for years with success for my Mathematica package TuGames (download tugames-v2.3.7z), that can be found here

TuGames Version 2.3

To have an idea how I use these libraries, I recommend to have a look on the third answer of the following question

How to plot a core of a cooperative game.

or for doing the same even in parallel have a look at

How to run an external program in parallel with a Mathematica package?

After you have compiled the libraries successfully, copy them in a bin-directory. Then call from a Mathematica session the following commands to open the links to Mathematica.

SetDirectory["/where/cddmathlink/is/located/bin64"]

cddml=Install["./cddmathlink"];
cddmlgmp = Install["./cddmathlink2gmp"];
cddml2=Install["./cddmathlink2"];

Alternatively, glance through the Mathematica file TuGames.m to get more ideas how to build up or close links with this library. You will also find in the README files some further instructions. If you need my Makefiles as templates, let it me know. I hope this helps.

Update 29.05.2016

Due to a private conversation, I saw some need to update my answer in order to overcome possible pitfalls which might occur during a compilation of the Cddmathlink binaries. My remarks are related to a Linux OS, but I am sure that with some small modification those are also applicable for Mac and Windows users.

First of all, do not use the mathlink.h header file that ships with the cddlib-094f.tar.gz archive file. This version is too old for Mathematica 8.x or higher. Instead of that use the mathlink.h and libML library that ship with your Mathematica version, and that should be located relatively to the Mathematica root directory, for instance, at

./10.3/SystemFiles/Links/MathLink/DeveloperKit/Linux-x86-64/CompilerAdditions

We see that we have to use the 64-bit version of the libML library. Do not try to link it against the 32-bit version. This will not work.

Furthermore, if the compilation of the libcdd libraries have been successfully terminated, the libcdd.a can be found relatively to the root directory cddlib-094h at

./lib-src/.libs/libcdd.a

Now, one has to adjust the following lines in the Makefile located in the src-mathlink directory to

ml : cddmathlink

     cddmathlink : cddmathlinktm.o cddmathlink.o cddmlio.o

        ${CC} -O3 -I${MLINCDIR} cddmlio.o cddmathlinktm.o cddmathlink.o -L${MLLIBDIR} ${MLFLAGS} $(LFLAGS) ../lib-src/.libs/libcdd.a -o cddmathlink

Similar for the src-mathlink2 directory, we have to adjust the Makefile to

ml : cddmathlink2 cddmathlink2gmp

    cddmathlink2 : cddmathlinktm.o cddmathlink.o cddmlio.o
         ${CC} $(LIFLAGS) -I${MLINCDIR} cddmlio.o cddmathlinktm.o cddmathlink.o -L${MLLIBDIR} ${MLFLAGS} ../lib-src/.libs/libcdd.a -o cddmathlink2

    cddmathlink2gmp : cddmathlinktm.o cddmathlink_gmp.o cddmlio_gmp.o
         ${CC} $(LIFLAGS) -I${MLINCDIR} cddmlio_gmp.o cddmathlinktm.o cddmathlink_gmp.o -L${MLLIBDIR} ${MLFLAGS} -lgmp ../lib-src-gmp/.libs/libcddgmp.a -o cddmathlink2gmp

If you still get some errors like "undefined reference to" invoke first a "make clean" in the folders above, and then rebuild it again. If the "undefined reference to" errors are still present, then change in the Makefiles the compiler to

#CC=/usr/local/bin/mcc
CC=/usr/bin/gcc

Execute again a "make clean", and then again a "make all". This should build clean and fine Cddmathlink binaries.

$\endgroup$
  • $\begingroup$ Thank you so much for your solution! But I'm afraid that I cannot adopt your solution, as I just accepted the solution of Igor Rivin a few days ago even though I still didn't figure out how to call Polymake functions from Mathematica directly. The good news is that I have succeeded in compiling the mathlink interface to cddlib and making it work properly a few months later after this question. But I really appreciate your cues on how to compile it years ago and your solution provided hours ago. $\endgroup$ – Han Xiao Apr 10 '16 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.