#8987: Add support for rational polyhedral fans
----------------------------------+-----------------------------------------
Reporter: novoselt | Owner: mhampton
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.4.4
Component: geometry | Keywords:
Author: Andrey Novoseltsev | Upstream: N/A
Reviewer: Volker Braun | Merged:
Work_issues: |
----------------------------------+-----------------------------------------
Changes (by novoselt):
* status: needs_review => needs_work
Comment:
Replying to [comment:9 vbraun]:
> 1) I agree that we should test `==` without identifying `GL(n,Z)` images
as it is expensive. But I'm afraid of the following, which is probably a
common use case:
{{{
sage: diamond = lattice_polytope.octahedron(2)
sage: P1xP1 = FaceFan(diamond)
sage: Cone([(0,1), (1,0)]) in P1xP1(dim=2)
False
sage: Cone([(1,0), (0,1)]) in P1xP1(dim=2)
True
}}}
You got a point here, I don't like this behaviour...
> Also, note that `Fan()` is implicitly sorting:
{{{
sage: fan1 = Fan([Cone([(1,0), (0,1)])])
sage: fan2 = Fan([Cone([(0,1), (1,0)])])
sage: fan1==fan2
True
}}}
There was no sorting, rays were determined first as a set (union of ray
sets of all cones) and then converted to a tuple. I am not sure if the
same set will always lead to the same tuple or it depends on something. I
definitely don't want to force sorting - if a user gives rays in a
specific order, then (s)he probably wants them in that order.
> I would argue that is is ok to treat fans and cones a bit different, one
will compare cones often but fans only seldomly. I'm happy with comparison
of fans to depend on the order of the rays and generating cones, otherwise
all derived quantities (like cohomology generators of toric varieties)
will not be equal (only isomorphic). But for `cone1==cone2` to depend on
the order of the rays is neither helpful nor intuitive.
In general, I agree, but it may potentially lead to `cone1 == cone2` while
`Fan([cone1]) != Fan([cone2])`. Are you OK with this?
As I understand, it is not enough to just add `__eq__` method to cones,
since it will conflict wiht `__cmp__` in the sense that it will be
possible to have `cone1 < cone2` and `cone1 == cone2` at the same time,
which is not cool. In fact, I do not see any good (and fast) way to
compare cones in agreement with mathematical equivalence. It will require
constructing `Polyhedron` objects for each cone to check strict convexity
and deal with possible non-uniqueness of ray generators, this will make it
highly undesirable to sort sequences of cones. It will also make hashing
of cones either slow or inconsistent with equality check (which is
accepted in Sage, but should not be the case unless necessary).
Yeah... I think my position is: I will do this change if you still want it
after arguments above, but I am very against it, especially since a method
performing mathematical equality check is provided. A compromise is to add
`__contains__` and `contains` to the `Fan` class so that one can do
{{{
sage: diamond = lattice_polytope.octahedron(2)
sage: P1xP1 = FaceFan(diamond)
sage: Cone([(0,1), (1,0)]) in P1xP1 # no (dim=2)
True
sage: Cone([(1,0), (0,1)]) in P1xP1 # no (dim=2)
True
}}}
It would be also nice, perhaps, to be able to check points in such a way,
i.e. if a point is in the support of a fan.
> 2) `Fan()` should always error out if the cones are not generating
cones. In particular, this one from the documentation
> {{{
> sage: cone1 = Cone([(1,0), (0,1)])
> sage: cone2 = Cone([(0,1), (-1,-1)])
> sage: cone3 = Cone([(-1,-1), (1,0)])
> sage: P2 = Fan([cone1, cone2, cone2])
> sage: P2.ngenerating_cones()
> 2
> }}}
> should have raised an exception.
>
> In normal use you'll never want to type in all the cones of the fan
since there are so many. But its easy to get confused and add a cone that
turns out to be not a generating cone, and its nice to catch this when
generating the `Fan`.
>
> There is certainly a need for a function that extracts the generating
cones from a collection of cones, but I don't think it should be implicit
in the Fan constructor.
My intention was to write a fan constructor that will construct a fan if
at all possible. (Similarly, the cone constructor by default will discard
non-generating rays.) One may, for example, start with some fan and add
more cones to it. In this case some of the old generating cones may become
unnecessary. Or, if cones of a fan come one by one from a certain
procedure (e.g. in computing GKZ decomposition) and it is not known in
advance how to easily select generating cones (e.g. all generating cones
are full-dimensional for complete fans), it would be nice if the fan
constructor could automatically select necessary cones. If you really
against silent discard, we can perhaps either add a warning about a non-
generating cone present, or a default parameter `generating_cones=True` to
`Fan(...)` and then throw an exception if there are such cones. If one
(like me ;-)) wants to discard them, it will be possible to use
`generating_cones=False` option.
> 3) Rename `Cone_of_fan.fan_generating_cones()` to `star_generators()`.
OK.
> There are similar methods to this one that we probably want to add
later, so let me just throw out some names:
> * `Cone_of_fan.faces()`: all subcones of the cone
> * `Cone_of_fan.facets()`: subcones of one dimension lower
Note that these are inherited from plain cones. However, they are likely
to be `ConeFace` objects and for fans it would make more sense to return
other `Cone_of_fan` ones...
> * `Cone_of_fan.bounds()`: supercones of one dimension higher
I don't like the name. I guess it means that `self` bounds those that are
returned by this function. But it can also be interpreted as that it
returns bounds of `self` in the sense its facets. How about `facet_of` for
this one?
> * `Cone_of_fan.star()`: the star of the cone
What exactly do you mean by `star` here? Do you want to get back the fan
in the quotient lattice? Anything else attached to it? I think we can use
coercion system to define the canonical map from the lattice of the
original fan to this one.
> * `Cone_of_fan.adjacent()`: Adjacent cones (of the same dimension)
Is this name standard? I see that it may be convenient to have such a
function, but I am not sure I would guess from the name what it does.
> 4) Do we need to know the set of ray indices, that is
`set(cone.fan_rays())`, of a cone often? Right now there is the function
`cone_to_rays(cone_index)` that is only used as a helper in
`cone_lattice()`. If it is just a helper function, then it should be
`_cone_to_rays()`. If you want to expose that functionality, it should be
stored in the `Cone_of_fan` and retrieved via `cone.fan_rays_set()` or so.
I think it is just a helper and can go to `_cone_to_rays` to clean up the
namespace.
> I also think that `cone.rays_idx()` would be a better name than
`cone.fan_rays()`, but if you disagree then I can live with the current
name as well :-)
I disagree, because `idx` is cryptic (indices?) and `fan_rays` clearly
tells one that it has something to do with the fan, even if it is not
obvious that it will return indices rather than rays. (But what else can
one expect? Rays themselves have no explicit relation to the fan.)
> 5) similarly to 4), `ray_to_cones()` is not very self-explanatory.
Agreed.
> We obviously need a way to find out which cones contain a given set of
rays. I would prefer one (or all) of the following
> * `ray_to_cone(ray_index)`: the 1-cone spanned by the ray
I was tempted to say that
{{{
sage: fan(1)[i]
}}}
will do exactly this, but it will not since `fan(1)` purposefully returns
the list of rays, rather than one-dimensional cones... Did you notice this
convention? What do you think of it?
Well, I think at least
{{{
sage: fan.cones(1)[i]
}}}
should do this work, even if it may fail to do so now because there is no
particular sorting of 1-dimensional cones in the lattice. This actually
seriously bugs me, since it was very annoying in `LatticePolytope` until I
fixed it. Fixing it for cones and fans was on my todo list for the future,
but I guess the best time to do it is now. Assuming that this will be
done, I propose to get rid of `ray_to_cones` (or perhaps rename it to
`_ray_to_cones`) and do not add `ray_to_cone`.
> * `smallest_cone_containing(*Nlist)`: the smallest cone containing all
points (which can be specified by a ray index or as a N-lattice element).
Can I remove `smallest_`? I think since `cone_containing` promises to
return a single cone, it is quite reasonable to expect that it will be
smallest (and of course it will be written in the documentation).
> The functionality of `ray_to_cones` would then be provided by
`ray_to_cone(i).star_generators()`.
Or, as I propose
{{{
fan.cones(1)[i].star_generators()
}}}
Let me know what you think now!
I am switching this ticket back to needs work. Regarding the last two
tickets in the sequence - while I am working on this one, you can probably
go ahead and review them too in the sense of comments. They will likely
need some minor changes after updating this patch, but I currently don't
plan to do anything else unless you request it.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8987#comment:11>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
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-trac?hl=en.
