=== Introduction === I would like to have the Parma Polyhedra Library (PPL) included as a standard spkg. My goal is to rewrite as much of the sage.geometry.* modules on top of a Cython PPL wrapper as opposed to piping ASCII to/from cddlib. Some of the reasons are:
* PPL is already faster by itself, and having a Cython wrapper reduces overhead. I'm seeing about 20x speedup on medium-sized problems. * PPL is the only polyhedral computation toolkit that is from the ground up designed to be used as a shared library.(1) * PPL is mature, well tested, has an active development including bug tracker and mailing list. It is used in a variety of other projects, including gcc's Graphite loop optimizer. It has been tested on Linux, FreeBSD, OpenBSD, Solaris, IRIX64, Mac OS X, Cygwin, DEC OSF/1. cddlib was the first really useful software package back in the day and it was hugely influential for many subsequent codes. But nowadays there are alternatives that combine the same algorithms with better implementations and software development practices.(2) Note that I'm not proposing to remove cddlib entirely. It is still a requirement for gfan and the only program to do polyhedral computations over floating point numbers.(3) === Work Plan === I have written a PPL spkg and a Cython (C++) wrapper that should cover all functions necessary for dealing with polyhedra in Sage. You can find it here: http://trac.sagemath.org/sage_trac/ticket/10039 Using this wrapper, I patched sage.geometry.cone: http://trac.sagemath.org/sage_trac/ticket/10140 I think that the PPL spkg and the Cython wrapper is ready for inclusion in the next Sage release (4.6.1?). In the subsequent release we can then rebase sage.geometry modules on top of the wrapper. Right now I would like to invite any comments on this plan! === Notes === (1) cddlib also comes with a shared library. But its poorly documented and, according to valgrind, leaks memory. Other toolkits like lrs and qhull don't build shared libraries but have minimal instructions for statically linking with parts of their code. (2) In particular, cddlib has no bug tracker, no new release in the last 5 years, and segfaults on some of its own testsuite. (3) Though in a numerically unstable way, see Trac #10046, #10037. -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
