There are some problems with the patch above: 1) the line lift_i *= 1.1 isn't good because usually we want rational or integer values for vertex coordinates. If numerical input is given (for the other vertices), these will just be cast to floats, but with exact input cddlib will try to do exact computations. 2) after changing this to lift_i = lift_i * 11/10, I could still find examples where it fails.
There is no doubt in my mind that lrs would be faster than anything you or I could produce in python. It is also code that has been tested by polytope experts (which I am not) for almost 10 years. If you want to keep trying, here's a particularly nasty 4D example whose vertices are: [[-97, -99, -61, 0], [-100, 93, -78, 0], [88, -100, 2, 0], [-34, 100, -65, 0], [96, 88, -10, 0], [64, -71, 99, 0], [-64, -100, -37, 0], [80, 86, -98, 0], [96, 91, -66, 0], [15, 99, -98, 0], [81, -95, -96, 0], [97, -50, 89, 0], [-92, 85, -97, 0], [56, 19, 100, 0], [98, 78, -63, 0], [-99, -100, 30, 0], [-13, -98, 97, 0], [-34, 34, 100, 0], [-15, -30, 100, 0], [95, -97, -75, 0], [94, -64, -92, 0], [94, -92, 46, 0], [98, 70, 63, 0], [-95, -52, 78, 0], [-94, -25, 95, 0], [83, 4, -97, 0], [-6, -100, -32, 0], [-6, 100, -45, 0], [-95, 81, 98, 0], [-79, 95, 97, 0], [100, -63, 56, 0], [90, -86, 94, 0], [35, -100, 94, 0], [-18, 99, 76, 0], [-48, -92, -91, 0], [-49, 94, -94, 0], [-99, 69, 69, 0], [-77, 100, 16, 0], [98, -76, -27, 0], [75, 98, 24, 0], [97, 71, -79, 0], [99, 24, -14, 0], [90, -97, 34, 0], [-88, 90, -91, 0], [-79, -14, -99, 0], [100, -72, 53, 0], [94, 97, -80, 0], [67, 99, 39, 0], [-95, -95, 54, 0], [66, 82, -99, 0], [-99, -73, -82, 0], [-58, -71, 97, 0], [-88, -36, -97, 0], [79, -41, 100, 0], [-82, -75, -99, 0], [-96, 90, 55, 0], [-99, 100, -71, 0], [-30, 100, 20, 0], [37, -9, -99, 0], [91, 84, -96, 0], [-66, 68, -98, 0], [92, 90, 98, 0], [43, -100, -19, 0], [-93, -91, -82, 0], [92, 1, 99, 0], [-87, -55, 96, 0], [34, 99, 77, 0], [-51, -27, 99, 0], [81, -95, 83, 0], [99, 69, 37, 0], [59, 100, 2, 0], [97, -62, -53, 0], [-20, 94, 99, 0], [39, 98, 86, 0], [96, -27, -87, 0], [100, -75, 24, 0], [0, 0, 0, 1]] lrs is almost instantaneous on that example, whereas both my code and yours fails. In the short term the current trac patch is still a big improvement over what was there before, so I think it should go in. Cheers, Marshall On Oct 7, 10:51 pm, "Arnaud Bergeron" <[EMAIL PROTECTED]> wrote: > 2008/10/7 mhampton <[EMAIL PROTECTED]>: > > > > > Linearly increasing the lift values does not work. I can find a > > relatively small example (81 vertices in 4 dimensions) where your > > patch fails. > > > For higher dimensions I think using lrs is really the way to go, since > > adding it has other advantages as well. When I have a little time I > > will try to write an interface to use it for triangulation. > > If it is faster, then go for it. But in the meantime I would like to > have something that works in all cases. > > If as I kind of guessed, but hoped to be false, linear increments are > not good because the may create planar situations in the extra > dimension, then an exponential growth should work. I have yet another > revised patch that does just that. > > After this one I promise to stop bothering you. > > Arnaud > > > I am putting the other improvements from your patch into another > > merged patch. Can you review it? > > > Cheers, > > Marshall > > >> On Oct 4, 7:59 pm, "Arnaud Bergeron" <[EMAIL PROTECTED]> wrote: > > >> > 2008/9/29 mhampton <[EMAIL PROTECTED]>: > > >> > > I thought I would explicitly point this one out because I had been > >> > > reviewing #4164 (work by Arnaud Bergeron), but now I am also > >> > > contributing code and I think the best scenario is to have someone > >> > > else take a look. Mike Hansen has looked at polyhedra.py before, so > >> > > he is a candidate if willing, but it would be great if someone else > >> > > takes a look. Polyhedra.py (in sage/geometry) is still in its early > >> > > stages; eventually I hope for it and other things in the geometry > >> > > group to provide most of the functionality of polymake and other > >> > > packages if they can't be made part of standard sage. Because the > >> > > optimal design is far from clear to me, I want to encourage more > >> > > eyeballs on it (I am an enthusiastic amateur when it comes to > >> > > polytopes, not an expert). > > >> > > Marshall Hampton > > >> > About this patch I have an idea for an improvement that would make it > >> > work 100% in all cases. I can't believe I didn't think of this > >> > sooner. > > >> > The idea is that instead of adding a random value in the extra > >> > dimension for the lifting we can only add an monotonically increasing > >> > value. I tried this on the simple 4D example that was in doctest > >> > before as well as the monster that crashed my code (and my hopes) > >> > before and they both worked repeatedly (with a newly created > >> > polyhedron, otherwise it just hits the cache). > > >> > I visualized the monster one (with ugly hacks) and the results looks > >> > correct. I haven't manually inspected every surface produced though, > >> > so there might be some errors. > > >> > So I turn to you (or anybody else that wants) for examples that could > >> > break this before submitting final version no 42 to trac. > > >> > Use the attached patch (requires trac_4164_merge.patch from the trac > >> > ticket) to try yourself or send me lists of vertices for polyhedron. > > >> > Arnaud > > >> > tentative_4164.patch > >> > 1KViewDownload > > > > tentative2_4164.patch > 1KViewDownload --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com 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 -~----------~----~----~----~------~----~------~--~---
