Re: [sage-combinat-devel] Re: Question about LatticePolytopeClass
Hi Johannes! On Sun, Jul 11, 2010 at 9:11 AM, Johannes wrote: > I want to derive a new class from latticePolytopes, because i did not > want to change the code and i needed the __eq__ (and some more methods) > on simplices and i don't want to use external methods using two arguments. > Otherwise, i have to check if i'm working with a reflexiv polytope or > not - so the other polytopeclass is not what i'm looking for. > I think i'll look through some of the tickets if i find something > interesting - computing the convex hull sounds or inside lattice points > sounds nice. Well, I think it is totally fine if you do change the code, especially if it is about adding new methods and functionality. Almost everything in the current module is written by me motivated by what I needed it for, which means that it probably does not do something (or even many things) needed by others, as in your case. The more people add methods that they need - the better it will be for everybody! Thank you, Andrey -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: Question about LatticePolytopeClass
Am 10.07.2010 19:48, schrieb Andrey Novoseltsev: [..] > By the way - what exactly do you want from polytopes in general? Why > did you want to derive a new class from lattice polytopes? There is > currently another version of polytopes in polyhedra module. Those > support rational and numeric base fields, arbitrary dimension and > unbounded objects. One big problem with both existing versions is that > they rely on external programs (PALP or cdd) for some basic > computations and those programs are called as system calls. This > creates huge overhead and makes working with large collections of this > objects (e.g. cones of a fan) difficult. Lattice polytopes have a > workaround but it cannot be used always. So ideally we should have > some fast polytope class which either does not use external programs > or calls them as libraries. Volker Braun (who is one of the authors of > polyhedra and toric framework) is looking at some options but he > probably will not have time in the near future to work on them. If you > want to help - that would be great! I think that the main things we > need are computing the convex hull and equations of facets. Next is > computing lattice points inside a polytope, and it would be desirable > to be able to do it for rational polytopes as well (PALP can do it > only for integral ones, and clearing the denominators and then > discarding extra points is not the way to go). > > Thank you, > Andrey > > I want to derive a new class from latticePolytopes, because i did not want to change the code and i needed the __eq__ (and some more methods) on simplices and i don't want to use external methods using two arguments. Otherwise, i have to check if i'm working with a reflexiv polytope or not - so the other polytopeclass is not what i'm looking for. I think i'll look through some of the tickets if i find something interesting - computing the convex hull sounds or inside lattice points sounds nice. greatz Johannes -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: Question about LatticePolytopeClass
On Sat, Jul 10, 2010 at 4:38 AM, Johannes wrote: > hey Andrey, Hi Johannes, > thnx for your information about __eq__ on latticepolytopes - i think > every coder understands ;). is there a patch with the new version, even > if it's not working? I'd like to have a look at it and maybe to do some > work there (if i find free time somehow) There is no new version for polytopes yet, but the idea is that lattice polytopes and their facets should behave close to cones/ray collections at trac #8986. (If you really want to look at the code, it would be best to apply all patches up to #8989 and then look at sage.geometry.cone, since it was modified significantly). > Am 09.07.2010 19:35, schrieb Andrey Novoseltsev: > > [..] >> I don't agree that elements of LatticePolytope are its integer points. >> As a set it is a subset of some real space, so usually it is infinite. >> > i don't agree here. the Points of the polytope depend on the space, > where it's defined in and a latticepolytope is always defined in on a > lattice, so the points of the polytope just can be latticepoints. But I > dont see any connection to a real space, maybe, ca connection to the > quotientfield of the lattice or to the algebraic clousure of it. In toric geometry lattice polytopes and rational cones are considered as objects in real spaces, so for this reason I would be against considering them mathematically as subsets of a lattice only. I definitely don't mind adding list and cardinality methods to behave like a finite set, but, for example, I want sage: 1/2 in LatticePolytope(matrix([[0,1]])) to return True (there is no "in" check currently). If there is strong desire and reason to have some polytope objects that are behaving exactly as finite sets, perhaps there should be some, but with a derived class (or just with some options to the constructor?) that will behave like a polytope in the real vector space. By the way - what exactly do you want from polytopes in general? Why did you want to derive a new class from lattice polytopes? There is currently another version of polytopes in polyhedra module. Those support rational and numeric base fields, arbitrary dimension and unbounded objects. One big problem with both existing versions is that they rely on external programs (PALP or cdd) for some basic computations and those programs are called as system calls. This creates huge overhead and makes working with large collections of this objects (e.g. cones of a fan) difficult. Lattice polytopes have a workaround but it cannot be used always. So ideally we should have some fast polytope class which either does not use external programs or calls them as libraries. Volker Braun (who is one of the authors of polyhedra and toric framework) is looking at some options but he probably will not have time in the near future to work on them. If you want to help - that would be great! I think that the main things we need are computing the convex hull and equations of facets. Next is computing lattice points inside a polytope, and it would be desirable to be able to do it for rational polytopes as well (PALP can do it only for integral ones, and clearing the denominators and then discarding extra points is not the way to go). Thank you, Andrey -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
Re: [sage-combinat-devel] Re: Question about LatticePolytopeClass
hey Andrey, thnx for your information about __eq__ on latticepolytopes - i think every coder understands ;). is there a patch with the new version, even if it's not working? I'd like to have a look at it and maybe to do some work there (if i find free time somehow) Am 09.07.2010 19:35, schrieb Andrey Novoseltsev: [..] > I don't agree that elements of LatticePolytope are its integer points. > As a set it is a subset of some real space, so usually it is infinite. > i don't agree here. the Points of the polytope depend on the space, where it's defined in and a latticepolytope is always defined in on a lattice, so the points of the polytope just can be latticepoints. But I dont see any connection to a real space, maybe, ca connection to the quotientfield of the lattice or to the algebraic clousure of it. greatz Johannes -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
[sage-combinat-devel] Re: Question about LatticePolytopeClass
Dear Johannes and Nicolas,
I was not on the list, but I joined, since I probably had to
anyway ;-)
Two main reasons for the reference equality testing for polytopes are:
1) I was new to Sage and Python when I wrote the first version of the
module, 2) I was too lazy for a long time. I do plan to severely
rewrite the code to make it behave closer to cones and fans
implemented by http://trac.sagemath.org/sage_trac/ticket/8986 and
http://trac.sagemath.org/sage_trac/ticket/8987 but it will probably
have to wait a few more months until we are done with toric varieties.
The correct behaviour of "==" in my opition would be to return
"s1.vertices() == s2.vertices()", i.e. not only I require all vertices
to be the same, but I want them to be listed in the same order. The
reason is that many methods of lattice polytopes depend on the order
of vertices and because it is fast. This is how cones and fans behave.
In addition, they have methods "is_equivalent" which test
"mathematical equality" without paying attention to the order. And
finally there are methods "is_isomorphic" to discard the choice of
bases.
On Jul 9, 7:33 am, "Nicolas M. Thiery"
wrote:
> By the way, Andrey, would you consider that the elements of a
> LatticePolytope are its integer points? If yes, could you add aliases:
>
> - cardinality -> npoints
> - points -> list
>
> for consistency with other FiniteEnumeratedSets? (and it would be even
> better if LatticePolytope was in that category).
>
> Should I open a ticket about this?
I remember our discussion on Sage Days 14 about it and it is still
hanging on my todo-list, sorry it is taking so long...
Part of the reason is that lattice polytopes are not very well
designed to fit into the picture in such a way - did you notice that
"p.points()" returns a matrix? I definitely don't want to have a
method named "list" returning a matrix ;-) On the other hand,
"p.facets()[0].points()" will return a list of integers, which are
indices of columns of that matrix.
I don't agree that elements of LatticePolytope are its integer points.
As a set it is a subset of some real space, so usually it is infinite.
Perhaps "points" is a misleading name and should be renamed into
"lattice_points". In any case, my current viewpoint is that it should
NOT return a matrix but rather a tuple or something similar. So far I
was not able to completely give up the idea of some fixed order of
points and being able to work with them using indices, so
FiniteEnumeratedSets didn't seem to be to attractive, since as I
understand there is no way to specify my own enumeration. (Am I wrong
about it?) For example, if we have a fan, we can specify a list of
rays and then give cones by (sorted) indices of this list. As I
understand such a representation will be faster for e.g. intersecting
cones then creating each cone based on rays only, because it is faster
to compare two integers rather then vectors. I just tried this:
sage: a = 1; b = 1; timeit("a==b")
625 loops, best of 3: 153 ns per loop
sage: N = ToricLattice(3); c = N(1,2,3); d = N(1,2,3); timeit("c==d")
625 loops, best of 3: 879 ns per loop
sage: e = vector([1,2,3]); f = vector([1,2,3]); timeit("e==f")
625 loops, best of 3: 4.62 µs per loop
I admit that I have not done any benchmarks on "real tasks" to see how
much working with indices will be faster, but struggling for speed I
computed the face lattice of the 6-dimensional cross-polytope in 0.3 s
instead of 8.36 in Polyhedron class (http://trac.sagemath.org/
sage_trac/ticket/8986#comment:18).
So, I plan to:
- make lattice polytopes live in lattices (http://trac.sagemath.org/
sage_trac/ticket/9062)
- switch internal representation of vertices and points to tuples of
immutable vectors (as cones/fans do)
- make vertices/points/interior_points/boundary_points return such
tuples as well (the problem here is that it will break backward
compatibility, so I don't know if I will be allowed to do it)
- instead of plain tuple above one can return something more
mathematical, with cardinality method.
Suggestions/recommendations are welcome! As well as on patches related
to toric varieties - the first batch got positively reviewed and I
hope they can be merged soon to decrease the length of our Mercurial
queue, but since they are new flaws can be fixed even if they do break
backward compatibility.
Thank you,
Andrey
--
You received this message because you are subscribed to the Google Groups
"sage-combinat-devel" group.
To post to this group, send email to sage-combinat-de...@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/sage-combinat-devel?hl=en.
