I support replacing cddlib with PPL for the default computation of exact polyhedra.
Eventually I would really like to see lrs as a standard component as well, because: 1) It is small and compiles on all our supported platforms. 2) David Avis has always been very responsive to any emails about lrs. 3) It uses a very different algorithm from PPL; sometimes it performs much better, and always with relatively little memory use. 4) It has been an optional package for a couple of years now, with no known problems. PPL can be the default, ideally with lrs as an optional backend. For numerical polytopes we should keep cddlib for now. Qhull might be the better long-term choice for numerical polytopes, since it was written from the beginning with that in mind. For now I am working on Qhull as an optional package (but its not very high on my priority list). -Marshall On Oct 18, 7:13 am, Volker Braun <vbraun.n...@gmail.com> wrote: > === 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
