Add fan morphisms

[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. attachment: trac_9972_add_cone_embedding.patch
2. attachment: trac_9972_improve_element_constructors.patch
3. attachment: trac_9972_remove_enhanced_cones_and_fans.patch
4. attachment: trac_9972_add_fan_morphisms.patch
5. attachment: trac_9972_fix_fan_warning.patch

See #9604 for dependencies.

CC: @vbraun

Component: geometry

Author: Andrey Novoseltsev, Volker Braun

Reviewer: Volker Braun, Andrey Novoseltsev

Merged: sage-4.6.2.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/9972

[novoselt]

comment:1

Attachment: trac_9972_add_toric_lattice_morphisms.patch.gz

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.

[vbraun]

Reviewer: Volker Braun

[vbraun]

comment:2

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?

[novoselt]

comment:3

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

[vbraun]

comment:4

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.

2. 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.

3. FanMorphism(lattice_hom, domain=Fan) constructs the image fan and uses it as codomain. Raise ValueError if not possible.

4. 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!

[novoselt]

comment:5

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!

[vbraun]

comment:6

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".

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).

Yes, sounds good!

4. 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".

[novoselt]

comment:7

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."

[novoselt]

Work Issues: switch to FanMorphism

[vbraun]

comment:8

1. I'll write a patch and post it here for the cohomology ring and divisor_group.

2. I don't see why we need the Enhanced* versions, then.

[vbraun]

comment:9

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...

[novoselt]

comment:10

Sounds good!

[vbraun]

comment:11

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.

[novoselt]

comment:12

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.

[vbraun]

comment:13

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.

[novoselt]

comment:14

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?

[novoselt]

comment:15

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.

[vbraun]

comment:16

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.

[novoselt]

comment:52

Indeed, it does not work and moreover - the error was in image_cone.

I have updated the main patch by adding a special branch for the image of the trivial cone and inserted your example into preimage_cones docstring.

[vbraun]

comment:53

Why is preimage_cones not the preimage of image_cones? This confuses me:

sage: cone =  f.image_cone( Cone([(1,0),(0,1)]) )
sage: [ cone is f.image_cone(c) for c in f.preimage_cones(cone) ]
[True, True, True, False, False, False]

I understand that it is working as documented, but it seems like it would be more useful to actually return the preimage cones. In other words, take preimage cones in the sense of fan morphisms and not in the sense of convex sets.

If one is interested in all cones mapping geometrically into a given cone one could always construct the Fan of the (fan morphism) preimage cones.

[novoselt]

comment:54

I am actually not quite sure I completely understand your comments, which makes me think that method names and definitions require some adjustments. How about the following:

• cones_mapped_into(cone) returning all cones of the domain fan mapped into the given cone of the codomain fan (this is what preimage_cones does now). They do form a fan, but I am not sure that it is a good idea to construct it, since we will loose connection to the domain fan then.
• cones_mapped_onto(cone) returning all cones of the domain fan whose image_cone is equal to the given cone of the codomain fan. Is this what you are talking about?
  In both cases we may add extra parameter to allow returning only maximal cones with these properties. Or we can add a function to fan module like maximal_cones(cones) that will select the maximal ones. In the case of cones of the same fan the selection process is not terribly expensive.

As for preimage_cones, I would say that preimage_cone would make perfect sense if it was just the set-theoretic preimage of a given cone, which in general is not strictly-convex and is likely to be not a part of the domain fan. I actually compute these cones internally for generating cones of the codomain fan, but I am not sure they have much value to the end user.

Thoughts?

[vbraun]

comment:55

I think the geometric image/preimage of a cone is not particularly useful for toric morphisms. A fan morphism maps cones to cones, but does not define linear maps of the individual cones. One should think of it as a map from the poset of domain cones to the poset of codomain cones. Or, in geometric terms, maps of the poset of torus orbits to the poset of torus orbits.

The usual blow-up example

sage: c1 = Cone([(1,0),(1,1)])
sage: c2 = Cone([(1,1),(0,1)])
sage: domain_fan = Fan([c1, c2])
sage: codomain_fan = Fan([Cone([(1,0),(0,1)])])
sage: f = FanMorphism(identity_matrix(ZZ,2),domain_fan,codomain_fan)
sage: ray = Cone([(1,1)])
sage: f.image_cone(ray)
2-d cone of Rational polyhedral fan in 2-d lattice N

means, geometrically, that the orbit closure P^1 corresponding to the cone ray (given by the relative star of ray) is mapped to the point corresponding to the f.image_cone(ray). Conversely, the preimage cones of f.image_cone(ray) are c1, c2, and ray. Geometrically, this means that the preimage of the point f.image_cone(ray) consists of the torus orbits (north pole), (south pole), C^* making up the fiber P^1.

[novoselt]

comment:56

Why a fan morphism does not define linear maps on individual cones? A fan morphism is a linear map between lattices, so it can be restricted to any (compatible) pair of domain/codomain cones and still induce a morphism between corresponding affine varieties. Just specifying mapping of fans as finite sets of cones is not sufficient, e.g. identity morphism and multiplication by 2 are different but obviously would induce the same cone correspondence. So since the actual linear map does matter, it makes sense to use preimages under this linear map. I agree that full (potentially non-strictly convex) preimages are probably of little use, we need to restrict to the domain fan, but I don't see why something called "preimage" should ever exclude the origin. In the sense of orbit closures it does correspond to the whole variety, but in the sense of affine patches it corresponds to the torus itself which is a part of any toric variety of the given dimension and always gets mapped to itself.

So I still propose the switch to cones_mapping_into for the current version and adding cones_mapping_onto for the version that you want to have. No preimage_cones at all since it is a confusing name in this context. On the level of toric varieties the corresponding methods may refer to orbits to make things clear, but here they are not present yet.

[vbraun]

comment:57

There is clearly important information in how the lattice spanned by a cone is mapped to a sublattice of the lattice spanned by the image cone. But that is just the restriction of the underlying lattice morphism, and not associated to just any cone of the domain. You never need the geometric image/preimage of a cone for toric geometry.

I would find it confusing if the FanMorphism contained any other "map of cones" than fan morphisms. Since there is no ambiguity in "image cone", there is no question about "preimage cones" in that category. If you want cones_mapping_into and cones_mapping_onto for implementation purposes that is fine, but image_cone and preimage_cones are what they are and should be called like that.

[novoselt]

comment:58

I kind of complained before that I don't quite understand the term "fan morphism" ;-)

From the beginning of the ticket:

Replying to @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.

So, as I understand we have a category with fans being objects. A fan is a collection of cones, each cone is a set of points. All cones of the fan sit in the same lattice, so there is also "the lattice of the fan."

Morphisms in this category are morphisms between lattices associated to fans, which map cones into cones as sets of points. So in particular they do define linear maps between individual cones as well, and I got lost when you said that they don't.

But I guess I agree that when we talk about images/preimages of cones, we should refer to the induced map between cones as a map between two finite sets, since we do not have a nice correspondence between cones as sets of points. Let me think a little more about it and post an updated patch.

[novoselt]

comment:59

I am convinced, the updated patch does what you have suggested and now preimage_tuple returns a tuple, as it was intended and documented. Thanks for the input!

[novoselt]

comment:60

Of course, I meant that preimage_cones returns a tuple...

[vbraun]

comment:61

In the aforementioned blow-up example, I get now

sage: f.preimage_cones(f.image_cone(ray))
(2-d cone of Rational polyhedral fan in 2-d lattice N, 2-d cone of Rational polyhedral fan in 2-d lattice N)
sage: filter(lambda c:f.image_cone(c).is_equivalent(f.image_cone(ray)), flatten(domain_fan.cones()))
[1-d cone of Rational polyhedral fan in 2-d lattice N, 2-d cone of Rational polyhedral fan in 2-d lattice N, 2-d cone of Rational polyhedral fan in 2-d lattice N]
sage: ray in f.preimage_cones(f.image_cone(ray))  # should be True
False

The preimage_cones misses the 1-d cone that maps to (in the fan morphism sense) the single 2-d cone of the codomain fan.

[novoselt]

preimage_cones implemented

[novoselt]

comment:62

Attachment: trac_9972_add_fan_morphisms.patch.gz

Grrr... That was due to my optimization attempt without proper thinking. The new version uses the same cycle as the very first one (which was finding everything and even more), but requires equality of image cones. Should work now, the blow up example in the documentation is extended to include the preimage cones of the quadrant...

[vbraun]

comment:63

Works great now!

[vbraun]

comment:65

For the tracbot:

Apply 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, trac_9972_fix_fan_warning.patch

[jdemeyer]

Merged: sage-4.6.2.alpha0