Hi everybody, This is mainly about making the lrs optional package standard to improve some polytope-related calculations.
My original motivation for lrs (linear reverse search) is that is a very different algorithm/implementation for computing exact convex hulls in arbitrary dimensions. Currently the default for this in Sage is cddlib, which uses the "double description" method. There are classes of polytopes for which lrs is much faster than cddlib, although in my experience cddlib does better most of the time. lrs is also nice in that it doesn't use much memory. Polymake also uses these two methods, plus a third, the "beneath and beyond" method. I still need to modify the Polyhedron class to make use of lrs if it is present. I am now thinking more about nice renderings of polytopes, and for that I need better triangulation code. I have a really bad algorithm in polyhedra.py right now that needs to be improved or replaced. I see at least three options for this: 1) I could just improve the code I already have. I've actually already done this, and I guess I will submit a ticket soon. But I am not an expert in this area and I don't think even my improved versions would be good enough for serious users. 2) The option I like best in the short term is to make lrs standard and use it for computing triangulations. The lrs algorithm computes a triangulation anyway, and its probably one of the faster methods available for doing so. lrs is small (spkg is 120kb) and compiles quickly. Its mature code, its been maintained and improved for about 10 years. 3) Eventually it would be good to add TOPCOM. Apparently it is what people use who do research that involves triangulations. But this is a bigger task than I can take on right now. Its a much larger piece of code than lrs, but it would add more functionality. So I can do option (1) very soon, and option (2) in the next month or so unless people have objections. To help, install the optional package and test it by downloading: http://www.d.umn.edu/~mhampton/lrs_test.ext and run $SAGE_ROOT/local/bin/lrs your_path_to_lrs_test/lrs_test.ext where of course you replace "your_path_to_lrs_test" with the path to the file. I've done this on a couple of intel macs (10.4 and 10.5), I don't expect any problems on linux and I have no idea about Solaris. Cheers, Marshall Hampton --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
