I would like a vote on including the lrs optional package as a standard package in Sage.
lrs stands for linear reverse search, an algorithm for computing convex hulls which is quite different from that of cddlib (which is already in Sage). You can read about the algorithm and initial implementation here: http://sage.math.washington.edu/home/mhampton/Avis_lrs_99.pdf One advantage of lrs is that the memory it uses is linear in the size of the problem (roughly speaking, see the reference for more precise statements). It can also be much faster than cddlib for certain families of polytopes. Because of this, polymake includes cddlib and lrs as well as its own third convex hull algorithm (beneath-and- beyond, which someone should implement in Sage one day). lrs can also compute triangulations and volumes of polytopes. We currently don't have anything else that can do those things, as far as I am aware. TOPCOM does all sorts of triangulations but it is a big, complicated program that would be much more difficult to include. Much as with polymake, it seems that the best way forward at the moment is to include the key smaller libraries and build our own functionality on them. lrs has been extended by David Avis since 1999. Because Komei Fukuda was a co-creator of it, its files are compatible with those of cddlib, which makes incorporating it into polytope code that uses cddlib very easy. It is a mature package that has had many rounds of bugfixes for its core functionality. lrs is pretty small - the optional spkg is 120 kB, which unpacks to less than 1 MB. The executable is only 92 kB on my machine. It buils qiuckly and I have seen no reports of build problems (although I don't know how many people have tried the optional package). I am cc'ing David Avis on this announcement in case he has any clarifications or comments. The license is GPL v2. Overall I think this is almost a model candidate for the sort of code that should be in Sage. Marshall Hampton --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
