Opened 9 years ago

Last modified 9 years ago

#9972 closed enhancement

Add fan morphisms — at Version 47

Reported by: novoselt Owned by: mhampton
Priority: major Milestone: sage-4.6.2
Component: geometry Keywords:
Cc: vbraun Merged in:
Authors: Andrey Novoseltsev, Volker Braun Reviewers: Volker Braun, Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by novoselt)

This ticket adds a module for fan morphisms - morphisms between lattices with specified fans in the domain and codomain, which are compatible with this morphism. Compatibility check and automatic construction of the codomain fan or refinement of the domain fan are implemented.

Patch order (applies cleanly to sage-4.6.rc0):

  1. trac_9972_add_cone_embedding.patch
  2. trac_9972_improve_element_constructors.patch
  3. trac_9972_remove_enhanced_cones_and_fans.patch
  4. trac_9972_add_fan_morphisms.patch
  5. trac_9972_fix_fan_warning.patch

Change History (54)

Changed 9 years ago by novoselt

comment:1 Changed 9 years ago by novoselt

  • Cc vbraun added
  • Status changed from new to needs_info

The patch is in principle ready, but while we are at it - do we want to make custom _repr_ for such morphisms? If yes, how should they be different from the standard?

Also, the speed is far from spectacular, but it is not easy to make it better until simple polyhedra work faster - currently most time is spend on constructing them for intersection purposes and I tried hard not to intersect more cones than necessary.

comment:2 Changed 9 years ago by vbraun

  • Reviewers set to Volker Braun

I don't have any good suggestion for how to improve _repr_, we can always leave that for later.

I'll rewrite the Polyhedron constructor in cython one of these days, that should fix the speed issues. Though its a good idea to minimize the number of intersections computed :)

The current version looks good for an initial shot at toric morphisms. Are you still changing things around or should I officially review it?

comment:3 Changed 9 years ago by novoselt

  • Status changed from needs_info to needs_review

I don't plan on changing these functions further, so this ticket is ready for review!

comment:4 Changed 9 years ago by vbraun

I like the functionality, but I'm confused about the name. Is this supposed to be a ToricLatticeMorphism or a FanMorphism? I am thinking that it would be good to split those apart, and perhaps make the latter inherit from the former.

ToricLatticeMorphism.make_compatible_with(fan) doesn't make the morphism compatible with the fan, it is the other way round. So it should be either fan.make_compatible_with(toric_morphism) or, say, ToricLatticeMorphism.subdivide_domain(domain_fan,codomain_fan). Or see below.

Another functionality that I would like to have is to figure out the image fan from the lattice morphism and the domain. How about the following proposal:

  1. separate ToricLatticeMorphism and FanMorphism.
  1. FanMorphism(lattice_hom, domain=Fan, codomain=Fan) constructs the fan morphism. If lattice_hom is a matrix the corresponding ToricLatticeMorphism is constructed automatically. Raises ValueError if the fans are not compatible.
  1. FanMorphism(lattice_hom, domain=Fan) constructs the image fan and uses it as codomain. Raise ValueError if not possible.
  1. FanMorphism(lattice_hom, domain=Fan, codomain=Fan, subdivide=True) will subdivide the domain fan as necessary.

Let me know what you think & I'd be happy to help, of course!

comment:5 follow-up: Changed 9 years ago by novoselt

  • Status changed from needs_review to needs_info

I am now putting finishing touches on plotting, but then return back to morphisms.

After actually working on morphisms a bit, I had second thoughts about class organization. In particular, I didn't see how FanMorphism can fit nicely into Sage and I didn't even understand what it is mathematically. A fan is a collection of cones with certain restrictions, right? Then a fan morphism should be a map between sets of cones, in our case finite. But that's not what we want, we rather want a morphism between supports of fans, which is given on points of the space by a linear map. Put it another way, we want a ToricLatticeMorphism restricted to the support of the domain. During construction of such a morphism we have to check that everything is compatible, which can be quite expensive. During any application of this morphism to a point, we should check that this point is in the domain and this is also non-trivial (the only thing that will work for general fans is checking this point against every generating cone). So if we do have a special class for FanMorphism, how about this definition: "it is a morphism between toric lattices with distinguished fans in the domain and codomain which are compatible with this morphism." I.e. the domain is still a whole toric lattice and there is no need for complicated checks. One can write then

sage: phi = FanMorphism(lattice_morphism, F1, F2)
sage: phi.image_cone(cone_of_F1)
<some cone of F2>
sage: phi.preimage_cones(cone_of_F2)
<a tuple of cones of F1>

Going further, I don't think anymore that we should derive special fans for domain/codomain of morphisms between toric varieties themselves, let's call this class ToricMorphism. The problem I have is that a single variety can be a (co)domain of different morphisms. (I definitely need such functionality.) This can make it very inconvenient to work with divisors and classes because they will get confused which parent do they belong to, we will have to work with coercion, and the code may need to look something like this:

sage: fan = ...
sage: X = ToricVariety(fan)
sage: fan = X.fan() # This is already a bit strange...
sage: phi = ToricMorphism(matrix(...), X, Y)
sage: psi = ToricMorphism(matrix(...), Z, X)
sage: X_fan_codomain = psi.codomain().fan() # These two lines are plain confusing
sage: X_fan_domain = phi.domain().fan()
sage: phi.domain().rational_divisor_group() == psi.codomain().rational_divisor_group()
???

All four fans above are mathematically the same, the only difference is what kind of extra functionality do they get. But they will be different Python objects and associated toric varieties will be also different objects for no apparent reason, i.e. how these reasons can be explained to a user rather than a developer?

So I think that either morphisms derive their own fans for domain/codomain and use them internally without actually changing the varieties they were created for (i.e. phi.domain().fan() is the same as X.fan(), but phi.domain_fan() can be something specialized), or they store this information in some other way and return (pre)images taking cones of usual fans as arguments.

I recall that we already had a similar argument in the beginning, whether or not we need any kind of specialized cones, which provide clean access to new features. I just checked how many new features got added:

  • TWO methods for Cone_of_fan: star_generators and star_generator_indices. (There were actually many new methods here originally, but others migrated to plain cones.) Still, I think that this class is justified, because these are very natural operations to perform on cones that belong to a fan. Also, a cone cannot quite belong to several fans in the sense that its internal data structures are severely tied to a fan and it is very important performance-wise. (E.g. intersection of cones of the same fan is incomparably easier/faster than for arbitrary ones, and this will remain true even when polyhedra are made fast.)
  • ONE method for Cone_of_toric_variety: cohomology_class. Here I feel less convinced that it is necessary, cone.cohomology_class() does not feel more natural to me than X.cohomology_class(cone). However, I think there are more methods added here by patches which are not applied in my queue and something else may come up during later development. If not, we should probably reconsider this class, because it would be nice to have
    sage: ToricVariety(fan).fan() is fan
    True
    
  • Hypothetical cones of (co)domain would each add one more method, but make it difficult/inconvenient to deal with multiple morphisms, while the whole point of making new classes should be making life easier...

For this ticket I propose the following:

  1. Rename make_compatible_with to subdivide_domain.
  2. Add to ToricLatticeMorphism a method like image_fan(domain_fan) to construct the "natural" fan in the codomain, as you have suggested.
  3. Add FanMorphism(ToricLatticeMorphism) which mathematically is what I have said above, will live in the same Hom-space as lattice morphisms, and will behave in the same way (including domain and codomain returning toric lattices), except that it also has domain_fan and codomain_fan methods returning fans which are guaranteed to be compatible with the morphism. It also has image_cone and preimage_cones, results are cached (perhaps it is more efficient to compute them at once for all cones or even do it during compatibility check).
  4. Cones of fans also get image_cone and preimage_cones methods that take as an argument a FanMorphism with appropriate fans.

A follow-up ticket will add ToricMorphism for arbitrary scheme morphisms between toric varieties and ToricEquivariantMorphism for those coming from FanMorphisms.

Let me know what you think!

comment:6 in reply to: ↑ 5 Changed 9 years ago by vbraun

Replying to novoselt:

"it is a morphism between toric lattices with distinguished fans in the domain and codomain which are compatible with this morphism."

Yes, that is the usual definition. No restriction on the support of the underlying lattice map.

On an unrelated note, I would call "point" = "0-dimensional torus orbit" = full-dimensional cone. A toric morphism maps points to potentially higher-dimensional torus orbits. Though I do understand that you meant lattice points.

I understand your issue about having multiple morphisms. But if the fans don't know about the toric morphism then they shouldn't know about the toric variety either, otherwise its confusing. So in principle I don't mind getting rid of the Cone_of_toric_variety class. At least this solves the dilemma cone_of_variety.cohomology_class() vs. variety.cohomology_class(cone); since the cone doesn't know about the variety only the latter can work. But instead of adding a cohomology_class method, I'd rather have the CohomologyRing element constructor accept cones:

  sage: HH = X.cohomology_ring()
  sage: HH( X.fan(2)[23] )

This pattern works already for the divisor group and Chow group:

sage: Div = X.divisor_group()
sage: Div( X.fan(1)[0] )   #  output should have been V(z0)?!?
V(1-d cone of Rational polyhedral fan in 2-d lattice N)
sage: A = X.Chow_group()
sage: A( X.fan(1)[0] )
The Chow cycle (1, 0, 0)

For this ticket I propose the following:

  1. Rename make_compatible_with to subdivide_domain.
  2. Add to ToricLatticeMorphism a method like image_fan(domain_fan) to construct the "natural" fan in the codomain, as you have suggested.

If we can agree on a hierarchy ToricLatticeMorphism -> FanMorphism -> ToricMorphism then ToricLatticeMorphism shouldn't know about fans at all, if only to avoid circular imports. Similar to how ToricLattice doesn't know about Fan. So make_compatible_with and image_fan become special cases of the FanMorphism constructor.

And instead of an is_compatible_with method, why not have FanMorphism(matrix,fan1,fan2) raise ValueError, "Cone <3,4,5> is not contained in any image cone".

  1. Add FanMorphism(ToricLatticeMorphism) which mathematically is what I have said above, will live in the same Hom-space as lattice morphisms, and will behave in the same way (including domain and codomain returning toric lattices), except that it also has domain_fan and codomain_fan methods returning fans which are guaranteed to be compatible with the morphism. It also has image_cone and preimage_cones, results are cached (perhaps it is more efficient to compute them at once for all cones or even do it during compatibility check).

Yes, sounds good!

  1. Cones of fans also get image_cone and preimage_cones methods that take as an argument a FanMorphism with appropriate fans.

I'd rather have only morphism(cone) (or morphism.image(cone)) and morphism.preimages(cone).

A follow-up ticket will add ToricMorphism for arbitrary scheme morphisms between toric varieties and ToricEquivariantMorphism for those coming from FanMorphisms.

I agree, but can we use, say, AlgebraicMorphism and ToricMorphism? Toric should really always be replaceable with "torus-equivariant".

comment:7 Changed 9 years ago by novoselt

  • Status changed from needs_info to needs_work
  • Work issues set to switch to FanMorphism

OK, I wanted to avoid "compatibility check by exception" but I can live with it ;-) How about this:

  1. Move cone.cohomology_class functionality to the element constructor of cohomology ring (I actually think this is the best and the most clear way there can be.) Can you perhaps make a patch for this change since it involves mostly your code?
  2. Get rid of Cone_of_toric_variety (that's my part so I can do this). This raises a question whether EnhancedCone/Fan should survive at all. One option is to put _ in front so that they disappear from the documentation.
  3. Make FanMorphism work as you have described, including informative error message.
  4. See if there is then any point in having ToricLatticeMorphism at all.
  5. No changes to cones, all (pre)images are computed/stored by morphisms. Which is probably also the cleanest way to do it.

I am also OK with ToricMorphism for equivariant ones. I'll see what name should fit nicely with existing classes for affine/projective morphisms for a "non-toric morphism between toric varieties."

comment:8 Changed 9 years ago by vbraun

  1. I'll write a patch and post it here for the cohomology ring and divisor_group.
  1. I don't see why we need the Enhanced* versions, then.

comment:9 Changed 9 years ago by vbraun

I'll also tighten x in fan to only return True if x is actually a cone. I'll add another method fan.support_contains(point) for the other usage. That'll make it easier to ensure that "something" is a cone of the correct fan. Otherwise we have stuff like 0 in fan return True...

comment:10 Changed 9 years ago by novoselt

Sounds good!

comment:11 Changed 9 years ago by vbraun

Patch is attached. I removed 'cohomology_class' from Cone_of_toric_variety to make sure that I got all occurrences, but tried to make as few other changes in that area as possible. Can you try to put my patch at the bottom of this ticket's queue?

I added an overriding method Cone_of_fan.is_equivalent (see the "TODO" comment) that you should uncomment after removing the enhanced cones.

The CohomologyRing._element_constructor_ now accepts cones as well. For the other issue, you should have complained that divisor_group returns the non-toric divisor group and only toric_divisor_group should accept cones ;-) The latter already works as it should.

comment:12 Changed 9 years ago by novoselt

Regarding Cone_of_fan.is_equivalent - cones of fan are also constructed by intersection method and during computing the cone lattice. They can certainly be non-unique now and I don't think that we should try to make them unique. So I propose removal of the overriding method.

comment:13 Changed 9 years ago by vbraun

My thought was that it can be expensive to ensure that two cones of a fan are not the same, and comparing ambient ray indices would be faster. And you always have to go through all cones of the fan to test membership, so it will be called often. I thought about whether that is a problem during the construction, but then I found it easiest to leave that question up to you ;-)

How about constructing Cone_of_fan always though a factory function that tests (via Cone.is_equivalent) if the cone is already in the fan. That would be simple to implement and we can then rely on uniqueness of the Cone_of_fan.

comment:14 Changed 9 years ago by novoselt

What membership exactly do you want to test?

The assumption is that there are no invalid cones of the fan, so if you want to check if a cone is in the fan, it is enough to check if the ambient fan of the cone is the fan in question. For checking equivalence of two cones of the same fan it is enough indeed to check that their ambient ray indices are the same, as tuples, since they are always assumed to be sorted and when they are not - it is a bug.

I don't mind adding uniqueness of cones of fan or even cones themselves for that matter (on a separate ticket, perhaps?), I just don't quite understand why do you want it. The advantages that I see are

  • memory saving;
  • cached data sharing;

and disadvantages

  • more complicated code for construction;
  • longer time for construction.

Do you have something else in mind?

comment:15 Changed 9 years ago by novoselt

Some more thoughts:

  1. When there is an attempt to check if a point is in the fan, should we try to interpret this point as a ray, i.e. 1-d cone?
  2. The last line of _contains should be replaced with the original version:
    try: 
        return data.is_equivalent(self.cone_containing(data.rays())) 
    except ValueError:  # No cone containing all these rays 
        return False 
    
    For example, if you take a fan which is a subdivision of a cone, then this cone will trickle down to this block, but cone_containing will raise an exception. There probably should be a test for such a situation (although I certainly don't claim that all other places test all possible exceptions...)
  3. Fan.contains should no longer accept many arguments after your change - let's replace *arg with cone.
  4. Typo: "or a something" should be without "a".
  5. Typo: "class associated to cones" should be "classes".

Otherwise looks great: the new approach allows users to create their own shortcuts and write HH(cone) instead of cone.cohomology_class(). While I like names exposed in Sage to be descriptive, I certainly don't want to force users do it in their code ;-)

I will base other patches of the ticket on top of this one.

comment:16 Changed 9 years ago by vbraun

A fan is a collection of cones. A point is never in a fan, as it is not a cone. I don't think we should make cones unique in general, only cones of a fan. You can have arbitrarily many cones (memory permitting), but the cones of a fan are a finite set; To me it then feels right to have the Cone_of_fan be unique. In the current implementation they actually are unique after the fan is constructed. So it ends up being a minor change to guarantee that they are always unique, I think.

comment:17 Changed 9 years ago by vbraun

One potential danger is that cone.ambient_ray_indices() is meaningless if cone is only mathematically equivalent to a fan, but not a Cone_of_fan. I've added a new method RationalPolyhedralFan.get_cone(cone) that finds the Cone_of_fan corresponding to the cone, and I tried to make sure it gets called wherever we accept arbitrary cones from the user.

But its a potential pitfall to watch out for. We could always insist on the user passing only Cone_of_fan, but that seems to be too unwieldy for the user. I would suggest that we move the ambient_ray_indices() accessor method to Cone_of_fan and convert the code in cone.py, fan.py to use the data member _ambient_ray_indices instead. All higher level functions then shall only use cone.ambient_ray_indices(), converting a generic cone to a Cone_of_fan via fan.get_cone(cone) if necessary.

Changed 9 years ago by vbraun

Updated patch

comment:18 Changed 9 years ago by novoselt

In what sense ambient_ray_indices is dangerous? If ambient structures of two cones are different, there is no point to look at these attributes at all. Otherwise they are the same if and only if cones are the same.

I am definitely against moving ambient_ray_indices to Cone_of_fan because the point in having it is uniform treatment of faces of cones and cones of fans, which are pretty much the same things. In fact, even star_generators make sense for faces of a cone in the sense of containing facets, it just should not be called that name. So currently the main reason for a Cone_of_fan to exist is that terminology for faces of cones and cones of fans is a bit different. I think that it should stay this way as much as possible, so that all cones behave the same.

I am also against new containment check - cones are equal if they have the same rays in the same order and equivalent if they define the same set of points. If the same cone happened to belong to different fans and so has two objects representing it, it does not change anything. We can check if cones belong to the same ambient structure for code optimization, but the output should be the same. Note that in this case this check actually can be done in generic cones and there is no need to override the method for Cone_of_fan.

I still don't understand exactly what are you trying to achieve in general and in particular why do we need get_cone method. I agree that fan.contains should return True only for (some) cones and not for anything else, because a fan is a collection of cones. I agree that it may be good to have uniqueness of Cone_of_fan but I don't see any reasons for doing this except for some performance gain and it is not clear how significant it can be. It also seems to me that it makes more sense to make all cones unique based on the ordered rays and the ambient structure, because essentially this is how cones of fans can be made unique.

comment:19 follow-up: Changed 9 years ago by novoselt

So for is_equivalent optimization I propose inserting

        if self == other:
            return True
        if self.ambient() == other.ambient():
            return self.ambient_ray_indices() == other.ambient_ray_indices()

in the beginning of Cone.is_equivalent. Maybe with == replaced with is in the if statements - both variants will work correctly, the question is how many simple but potentially non-informative checks we want to perform before using a generic algorithm.

comment:20 in reply to: ↑ 19 Changed 9 years ago by vbraun

Replying to novoselt:

In what sense ambient_ray_indices is dangerous? If ambient structures of two cones are different, there is no point to look at these attributes at all.

Thats of course true, but we got that wrong in the ToricDivisor constructor (no check that the ambient was the same) and you didn't catch it ;-)

I'm just trying to explore options that make it impossible to make this mistake in the future. One more idea would be to force the user to pass the ambient to ambient_ray_indices(),

sage: fan1 = ...
sage: fan2 = ...
sage: fan1.generating_cone(2).ambient_ray_indices(fan1)   # fast
sage: fan1.generating_cone(2).ambient_ray_indices(fan2)   # slower

This would also get rid of the need for get_cone()

The point of the get_cone method is to avoid this extra branch whenever the user passes a cone that is not necessarilly within the same ambient:

    if is_Cone(c):
        if c.ambient()==fan
            indices = c.ambient_ray_indices()
        else:
            try:
                indices = tuple(sorted([ fan.rays().index(r) for r in c.rays() ]))
            except ValueError:
                ...

and instead just write

    if is_Cone(c):
        indices = fan.get_cone(c).ambient_ray_indices()

comment:21 Changed 9 years ago by novoselt

Aha, now I see! I really don't like the idea of forced arguments to ambiet_ray_indices and get_cone seems to be a confusing name. How about this:

  1. Implement get_cone functionality using __call__ for fans and cones, i.e. you will have to write fan(c).ambient_ray_indices() to make sure that indices are correct. The same goes for other relative things like face walking methonds - in all cases it is assumed that your cone knows where does it sit. This goes very well with the concept of fans being collections of cones - you "convert" a certain cone to an element of this collection. For cones it is not as transparent but still makes perfect sense, IMHO.
  2. In principle, I don't terribly mind adding *optional* argument so that one can write c.ambient_ray_indices(fan) and internally it will be translated to fan(self).ambient_ray_indices(). However, I then want to have it for all functions where it does make sense, it will add the same piece of code and documentation to all of them, and in the user code it does not lead to any significant clarification or space saving. So I'd rather not add such functionality and you don't usually like having two different ways to do the same thing ;-)
  3. Leave equivalence and containment checks mathematical, i.e. it is possible to get True for a check that a cone of one fan is "in" another fan. Those who want to check if it is an actual element of the collection should use cone.ambient() is fan.

If you agree with these proposals, then I can start implementing them and uniqueness of cones (and then fans too for uniformity, I guess) working on top of your patch.

comment:22 Changed 9 years ago by vbraun

Adding the functionality to __call__ still does not enforce that ambient_ray_indices is used correctly. In particular, it would not have caught the bug in ToricDivisor.

How about we remove the ambient_ray_indices() method from cones altogether and replace it with fan.ray_indices(cone).

I agree with 3.

I don't think that the Cone_of_fan uniqueness is particularly urgent, we can come back to that later.

comment:23 Changed 9 years ago by novoselt

It is not quite Python style to try to eliminate any possibility of user mistakes by making sure that everything is called properly in proper places. The assumption is that users know what they are doing ;-) These methods assume that your cone is in some fixed fan:

  • adjacent
  • ambient_ray_indices
  • face_lattice (indirectly - since elements will be cones of the same fan)
  • faces (indirectly)
  • facet_of
  • facets (indirectly)
  • star_generator_indices
  • star_generators

All of these methods are pretty important and convenient, in particular, in many cases ambient_ray_indices is more useful than rays or ray_matrix since it allows you to see clearly how different cones are related to each other. It would be quite annoying if for using all these methods it was necessary to mention fan explicitly.

Yes, there are bugs that appear because users make wrong assumptions, but I don't think that it is a valid reason to require users to always explicitly state all of their assumptions so that each function can check that they are correct and when possible fix them.

In addition, as you pointed out in a sample code above, passing ambient explicitly will mean that it always works correctly, but sometimes fast and sometimes slow. This sometimes slow can be sometimes significantly slow and the reason for keeping track of these ray indices and ambients is precisely code optimization, otherwise all cones could store only their rays and all fans - only their cones.

So I still think that if you have a cone and it is important that things about this cone are computed relevant to a certain fan, you are responsible for making sure that this cone "sits" in this fan and if not - trying to convert it there. I see a point in making this conversion easy, but not in making it mandatory every time you need it. Compare this

sage: indices = fan.ray_indices(cone)
sage: supercones = fan.cones_with_facet(cone)

and this

sage: indices = fan(cone).ambient_ray_incides()
sage: supercones = fan(cone).facet_of()

I think in the second case it is quite clear that

sage: cone = fan(cone)
sage: indices = cone.ambient_ray_incides()
sage: supercones = cone.facet_of()

is likely to be faster, plus it is a bit easier to read and there is only one place where an exception can occur due to cone being incompatible with fan at all.

I also think that using cones from a wrong fan is likely to be exposed very quickly in actual work due to index-out-of range exceptions, so given several month of working with current interface, I really don't want it to change...

comment:24 Changed 9 years ago by vbraun

Well face_lattice, faces, facet_of, and facets should return mathematically equivalent results if the cone is in the wrong ambient, so they don't count. For adjacent and star_generators I would tend to let your argument pass that the output would be so wildly wrong that it is immediately obvious. But ambient_ray_indices of a Cone always returns valid index ranges (namely, range(0,cone.nrays())).

So I do maintain that this method is particularly dangerous. Note that I don't want to get rid of the _ambient_ray_indices data member, just

def ray_indices(self, cone):
    if self is cone.ambient():
        return cone._ambient_ray_indices
    # slow fallback

comment:25 Changed 9 years ago by novoselt

Well, if you just want to add fan.ray_indices(cone) method (which can be potentially slow), I am OK with it, although I'd rather not ;-) But I really want to keep cone.ambient_ray_indices() as is without any arguments, especially forced ones.

And I still think that the best way is to explicitly convert input cones to cones of a particular fan and then freely use any fan-dependent methods. Given the current size of toric code it does not seem to me that we have any particularly dangerous methods (the most dangerous are check=False and normalize=False options, which are described as dangerous). So maybe instead of changing code we can put a warning in the documentation that this method may be dangerous and one should ensure that cone.ambient() is what it should be before calling this method. It seems to me that it is quite difficult to start using ambient_ray_indices without reading its documentation at least once.

comment:26 Changed 9 years ago by vbraun

I agree that the best way is to first convert the input cone to the fan and then work with that.

But 1) its easy to accidentally omit that step and 2) it is very hard to detect that you got it wrong. In my book, thats a very dangerous API design. I don't think a warning in the documentation is sufficient here, after all, we should have known better yet we fell into that trap with ToricDivisor.

At the very least ambient_ray_indices() should spit out a warning if self==self.ambient() [what ARE you trying to do?]. But the best option seems to me to be the fan.ray_indices(cone) method. If you wrote your code correctly there won't be any slowdown, and if you forgot to convert the cone to a cone of the fan then you'll still get the right answer. Ideally we'd then make ambient_ray_indices private not use it outside of cone.py/fan.py (and fan morphisms).

comment:27 Changed 9 years ago by novoselt

After some more contemplating and checking

$ grep "ambient_ray_indices()" sage/geometry/* |wc
     30     179    2579
$ grep "ambient_ray_indices()" sage/schemes/generic/* |wc
     13      85    1383

on Sage-4.6.alpha3, I think that you may be a bit overestimating the danger. We have used this function in 43 places and so far everything is working quite well. The "mistake" you ran into got quickly caught even before the ticket got ready for a review. Also, why did you get this mistake? Because you took a code from a place where the ambient definitely was set correctly and moved it to the place where potentially other cones maybe passed in. Finally, you actually have not done any mistake, you just left a possibility for a user to make one by passing a wrong cone. (In this case, I think, the mistake would be realized quite fast even if the code did not throw up an exception.)

Adding a warning for calling ambient_ray_indices on the ambient itself may not work because it may be called internally in some cycles. (I didn't check but it is quite likely.) Besides, nothing is wrong with such a call. I also strongly believe that this method must be open/documented/public, because if we have used it in 43 places, it is quite important for development and therefore users who build their own structures on top of stuff shipped in Sage are likely to find it convenient in their code. I personally use it all the time when working with varieties and sometimes even regret that these indices are not the default output for cones, so when I have a list of them I need to write a cycle calling this method.

A few months ago I already suggested switching to notation like fan.ray_indices(cone) etc. but you opposed and pointed out that it is not in the spirit of OOP. Now I actually completely agree and think that it is very fortunate that we have not done so then. I even still see some benefits of having special classes for cones of toric varieties and morphisms (in particular, this problem would not occur ;-)) but for these cases the disadvantages overweight.

Have I convinced you yet or should I abandon any hope?-)

comment:28 Changed 9 years ago by vbraun

I had counted the occurrences of ambient_ray_lattice as well, but my conclusion was that it is seldomly used outside of /sage/geometry/cone,fan.py. Replacing the 13 occurrences wouldn't be hard. The fact that copy/pasting "correct" code turns it so easily into "incorrect" code is precisely what I find disturbing. Also, the mistake in ToricDivisor was not caught easily. It is in the current release. And saying that its the user's fault ("You are holding it wrong" :-) is not helpful.

comment:29 Changed 9 years ago by novoselt

I meant that mistake would be realized quite fast once the code was actually used. I didn't actually use code for toric divisors yet, especially with cones from another fan. But anyway - this is all hypothetical and I may be very wrong.

My main point is not that it is difficult to replace 13 uses of ambient_ray_indices, but that it is a very convenient and natural function which I personally use both when developing new code and when actually using Sage interactively. I would rather not pass any arguments to it, because it is annoying for interaction and in functions it may lead to code like

cone.ambient_ray_indices(cone.ambient())

or

cone.ambient().ray_indices(cone)

which is plain confusing.

The name of the function clearly indicates that there is something ambient and cone must be aware of it, since no arguments were passed. Therefore, when using this function, the user should be sure that this something ambient is what it is supposed to be. In fact, it may be more clear for new outside users than for us, since we are used to writing code inside the class where in many cases this requirement is definitely satisfied. (How can self have a wrong self.ambient()???) And after all this discussion I will probably remember very well for a long time to make an extra check that this function is used after making sure that ambient is what it is assumed to be.

If you want to add extra functionality like fan.ray_indices(cone) which will be safer to use and then use this one when you want - I am fine with it. But if you insist on getting rid of cone.ambient_ray_indices() in its present form/namespace, we need to invite more people from sage-devel for opinions...

comment:30 Changed 9 years ago by novoselt

By the way, in schemes ambient_ray_indices is used several times in the examples and it was also used in Hal's examples for their book. It is very-very natural and should be as easy to access as possible...

comment:31 Changed 9 years ago by vbraun

ambient_ray_indices is not natural! Natural operations on cones should work without referring to a particular enumeration of the rays. Think cone1.intesection(cone2) vs. set(cone1.ambient_ray_indices()).intersection(set(cone2.ambient_ray_indices())). Of course sometimes you can't avoid it, definitely not in the internal implementations, but higher-level code (like the toric varieties) could easily move away from it. Case in point is that it is used only 9 times (the other 4 are in doctests).

And this looks horrible

cone.ambient().ray_indices(cone)

precisely because it is bad! It will break things! Its like a big, flashing sign: Do not write this code! You really want to use self.fan().ray_indices(cone)!

I don't mind the availability of cone.ambient_ray_indices() so much if you use it on the command line; In that case you know what your ambient() is. But I think we should ban its use from the toric varieties code. Then we algorithmically audit it for correctness by grepping sage/schemes/generic for ambient_ray_indices. How does that sound?

comment:32 Changed 9 years ago by novoselt

Well, instead of "very-very" let me say that ambient_ray_incices are as natural as coordinates. Coordinates may be not very convenient for definitions, since you need to make sure that the choice of the coordinate system does not matter. They are in many cases not mathematically natural in the sense that there are many different choices without any preference. At the same time they are quite useful both for proofs and for working with concrete examples.

Now, choosing between cone.ambient_ray_indices() and fan.ray_indices(cone) is like choosing between always mentioning which coordinate system you are using whenever you use coordinates and having some coordinate system "understood from context." Of course, in the second case you are risking to encounter a situation when it was not quite clear and it leads to mistakes since coordinates in one system may have very little to do with coordinates in another one. People do such mistakes from time to time, that's just life. But it is very convenient to have this default and I still vote for it despite the mistake that you have discovered. (By the way - how did you find it?)

Leaving a function but banning it for internal use is a bit silly - the way to enforce it is to scan for occurrences of this function and then replace it with a "safe version". If you do it, then the second step can be making sure that it is used safely and correctly.

comment:33 Changed 9 years ago by novoselt

In an effort to be less stubborn, here is what I think I should do if we cannot live with the existing interface:

  1. Keep internal fields _ambient and _ambient_ray_indices which can be related either to a cone or a fan (from the coding point of view these situations are similar and it is very convenient to treat them together - I know for sure since my initial version didn't do it).
  2. Remove ambient() and ambient_ray_indices() methods. In the code we still can use attributes since they always must be set in the constructor. Also remove adjacent and facet_of methods from cones and star_generator_indices and star_generators from cones of fan. The class Cone_of_fan becomes completely unnecessary and should be discarded.
  3. Add methods corresponding to the above ones with respect to an explicit ambient (of course, there is no analog for ambient itself anymore):
    sage: ambient_cone.ray_indices(cone)
    sage: ambient_cone.adjacent_faces(cone)
    sage: ambient_cone.faces_with_facet(cone)
    sage: fan.ray_indices(cone)
    sage: fan.adjacent_cones(cone)
    sage: fan.cones_with_facet(cone)
    sage: fan.star_generators(cone)
    sage: fan.star_generator_indices(cone)
    
    Cones still will cache all this stuff for their own _ambient in a hope that it will be useful later and that's how usually they will be called.

But I still need some voting before performing such a change.

I still think that it is convenient to have a default for "the thing before dot" above. This opinion is based on actually working with such structures, so maybe I have bad habits, but that's what I prefer. I also still think that it is natural in mathematics. E.g. Fulton on p.52 defines Star(tau), where it is assumed that tau is a cone in some fan. In a lot of papers using reflexive polytopes people introduce some notation for dual faces. I have never seen such a notation mentioning the ambient polytope, yet the notion of a dual face does not make sense without one. One can argue that a face is supposed to know its ambient, because it is a face and not just a standalone polytope. But with this line of thoughts I think toric divisors may require a cone of an appropriate fan as an input. Or we can agree that we will use any input cone and try to interpret it as a cone in this appropriate fan, in which case it is our responsibility to ensure that we do such an interpretation correctly. It is also common to fix some index set and then use it to index rays of the fan, their generators, corresponding homogeneous variables, and divisors. So I still think that these indices are relevant beyond the implementation guts of cones...

comment:34 follow-up: Changed 9 years ago by vbraun

I don't want to rewrite the entire interface, and I think that having some implicit assumption about what the ambient() is is usually fine. Also, 3.) is spectacularly ugly :-P As I said before, if the method call e.g. returns again a collection of cones then you'll immediately notice that you had the wrong ambient(). The difference with ambient_ray_indices is that its output will fail in much more subtle ways if the hidden assumption is wrong.

If you desperately want to keep ambient_ray_indices(), how about we prefix any use in the toric varieties code with an assertion that makes it explicit. This would be yet another way to make the implicit assumption explicit and have it easily machine-verifiable.

On an unrelated note, I don't like cone_of_fan = fan(cone), its too similar to Fan([cone]). How about Fan.cone_equivalent_to(cone), see also the already-existing similar method Fan.cone_containing(cone).

comment:35 in reply to: ↑ 34 Changed 9 years ago by novoselt

Replying to vbraun:

3.) is spectacularly ugly :-P

I wholeheartedly agree ;-)

If you desperately want to keep ambient_ray_indices(), how about we prefix any use in the toric varieties code with an assertion that makes it explicit. This would be yet another way to make the implicit assumption explicit and have it easily machine-verifiable.

I desperately want to keep it! I think that assertions are great - I don't use them much mostly because I didn't know about them until reviewing some of your code, but I am totally for them. However using them always before ambient_ray_indices() is too harsh - I went through cone.py, fan.py, toric_variety.py, fano_toric_variety.py and in all cases it was actually already clear that cone._ambient is correct, e.g. because cone was constructed in the same code. So I think that more generally we should use assertions for input parameters, which was the problem in this case.

On an unrelated note, I don't like cone_of_fan = fan(cone), its too similar to Fan([cone]). How about Fan.cone_equivalent_to(cone), see also the already-existing similar method Fan.cone_containing(cone).

fan(cone) is similar to Fan([cone]) only if your fan is called fan ;-) I was thinking of such format to mimic Element-Parent behaviour in Sage, but:

  • currently we don't use this model for cones and fans;
  • if we did, then cones must be both elements (of fans) and parents (of points), and this is not yet supported in Sage;
  • I don't clearly see advantages of such a switch;
  • I would like to have the same interface for "putting" cones into fans and faces into cones.

So the attached patch implements for cones and fans methods embed(cone). cone_equivalent_to seems unclear to me despite of being long, but I am not sure if embed is much better - what do you think of it? Maybe embed_cone/embed_face would be more clear?

I propose a bit different implementation of this method than in your patch. For fans it computes potential ray indices and then uses cone_containing method. This should be faster than using cone_containing directly on the rays and does not trigger cone lattice computation. For cones it will go through all faces of the relevant dimension, but instead of checking cone equivalence it still computes potential ray indices and then looks for a face with them. It will not work for non-strictly convex cones, where I also check for equivalence. (Although it will not work yet anyway - we cannot compute face lattice in such a case.) Documentation is mostly the same for fans and cones, but I tried to explain and illustrate clearly what the function does and why one should care.

I have also tweaked Fan constructor a little bit - now rays of the fan generated by a singe cone will have the same order as this cone. Shuffling bugged me some time before and again now that I was writing doctests for embeddings. My general attitude to such situations is that users enter data in the way they like, so it is good to preserve it as much as possible.

comment:36 Changed 9 years ago by novoselt

P.S. I also optimized is_equivalent for cones of the same ambient, as was suggested in http://trac.sagemath.org/sage_trac/ticket/9972#comment:20.

comment:37 Changed 9 years ago by novoselt

Fixes for non-strictly convex cones: cone --> self for convexity check in Cone.embed and extra convexity check in Cone.is_equivalent for the case of common ambient (does not require extra computations for cones of fans, they are always directly set to be strictly convex).

comment:38 Changed 9 years ago by vbraun

I couldn't figure out whether your patch goes before or after mine, so I folded it into one and fixed everything.

I changed

        # Optimization for fans generated by a single cone
        if len(cones) == 1:
            cone = cones[0]
            return RationalPolyhedralFan((tuple(range(cone.nrays())), ),
                                         cone.rays(), lattice,
                                         is_complete=lattice.dimension() > 0)

to is_complete=(lattice.dimension()==0).

Now that we agree on this ;-) can you go ahead and remove the Enhanced* versions of fans and cones? Then we can go on with fan morphisms...

Changed 9 years ago by novoselt

Changed 9 years ago by novoselt

comment:39 Changed 9 years ago by novoselt

Oops, sorry - I should have written that it was supposed to be the first. I unfolded the patches back so that it is clear who is writing/reviewing what and we don't need to seek the third person for the final review. I have updated my patch to fix the mistake that you caught. In your part I have removed is_equivalent from Cone_of_fan since this optimization is now performed by general cones. I have also removed extra parenthesis from cone = fan().embed(x).

I also have one more issue with your patch which got lost above, regarding new containment check: cones are equal if they have the same rays in the same order and equivalent if they define the same set of points. If the same cone happened to sit in different fans (or cones, for that matter) and so has several different objects representing it, it does not change anything. We can check if cones belong to the same ambient structure for code optimization, but the output should be the same. Also, to me it feels perfectly natural to ask e.g. whether a cone of some fan belongs to a subdivision of this fan. So I think that cone in fan should return True if cone is equivalent to any of the cones of fan. What is the ambient structure of cone and what is its ray order does not matter. If you really disagree with this, then I think that cone in fan should return True ONLY if cone.ambient() is fan is True. But I definitely prefer the first variant. Then one can write

sage: if cone in fan:
sage:     cone = fan.embed(cone)
sage:     Do something, say with cone.adjacent()
sage: else:
sage:     Deal with it somehow.

Changed 9 years ago by novoselt

comment:40 Changed 9 years ago by novoselt

Enhanced cones are removed, all tests pass. Current ticket queue: last three patches then the first one (which is going to be changed).

comment:41 Changed 9 years ago by vbraun

I agree with cone in fan meaning that cone is equivalent to any cone of the fan. I updated my patch to reflect this.

comment:42 Changed 9 years ago by vbraun

Oops I had forgotten to refresh the patch. Correct version follows.

Changed 9 years ago by vbraun

Updated patch

comment:43 Changed 9 years ago by novoselt

I'll post an updated patch with FanMorphism shortly.

Regarding image_cone and preimage_cones - I guess we want them to work for arbitrary cones of domain/codomain fans. In this case it is still clear what to return for image_cone(cone) - the smallest cone of the codomain fan which contains the image. But what about preimage_cones? Should we return all cones that are mapped to it, or only maximal ones? (We can also consider packing them into a fan, but in this case we loose connection with the domain fan, so I don't think that it is a good idea.)

I am also not sure what would be an efficient way to determine preimage cones. I am thinking about determining rays that are mapped into the given codomain cone and then scanning trough all domain cones to see which are generated by such rays only. An alternative approach, which is likely to be better for intensive work with such cones, is to compute full dictionary for image cones and then revert it to get preimage ones. Any suggestions?

comment:44 Changed 9 years ago by novoselt

  • Description modified (diff)
  • Summary changed from Add toric lattice morphisms to Add fan morphisms
  • Work issues changed from switch to FanMorphism to implement preimage_cones

I am attaching a patch that does not compute preimage_cones yet, but the rest is claimed to be ready for review/comments. I have removed classes for lattice morphisms themselves since they were not adding anything anymore. All of the old functionality is moved to FanMorphism constructor as you have suggested above. Codomain fan can now be omitted and will be computed, if possible.

This feature has exposed a problem I mentioned (I think) when we were adding warnings to the Fan constructor. The image fan is generated by images of cones of the original fan and these images may coincide or become non-maximal. As a result, one of the doctests fails due to the warning that some cones were discarded and users may see such a message as well, which will be quite confusing, I think. What should we do? Add a parameter to Fan(..., warn=True) and set it to False explicitly in the internal code?

Current queue:

  • trac_9972_add_cone_embedding.patch
  • trac_9972_improve_element_constructors.patch
  • trac_9972_remove_enhanced_cones_and_fans.patch
  • trac_9972_add_fan_morphisms.patch

comment:45 Changed 9 years ago by novoselt

  • Status changed from needs_work to needs_info
  • Work issues changed from implement preimage_cones to Warning from Fan constructor

OK, preimage_cones can now be computed, everything is doctested, the last issue is with warnings.

Changed 9 years ago by novoselt

comment:46 Changed 9 years ago by novoselt

  • Authors changed from Andrey Novoseltsev to Andrey Novoseltsev, Volker Braun
  • Reviewers changed from Volker Braun to Volker Braun, Andrey Novoseltsev
  • Status changed from needs_info to needs_review
  • Work issues Warning from Fan constructor deleted

After some more contemplating, I don't really see any other solution to the problem except for adding a parameter to suppress warnings. (Well, the other option is to remove the warning completely, but I have a feeling that it will not be accepted ;-)) So the last patch does exactly that, now all doctests pass smoothly and I propose merging this ticket.

For the record: I am giving positive review to the current "trac_9972_improve_element_constructors.patch" written by Volker Braun.

comment:47 Changed 9 years ago by novoselt

  • Description modified (diff)
Note: See TracTickets for help on using tickets.