Add lattice computations for convex polyhedral cones

[vbraun]

Various computations in toric geometry rely on the (saturated) N-sublattice generated by a cone and its complement and projections onto these. And, similarly, for the dual cones in the M-lattice. This patch adds what is necessary for Chow group and sheaf cohomology computations later on.

See tracker bug at #9604 to for the patch queue/dependencies.

CC: @novoselt

Component: geometry

Author: Volker Braun

Reviewer: Andrey Novoseltsev

Merged: sage-4.6.alpha1

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

[novoselt]

comment:2

Hi Volker,

I have a bit limited computer time this week, so I can be slow in responses and will probably wait till next week for final positive verdicts.

Comments on the current version:

1) ray_basis assumes that rays start from a linear independent set. I would rather not make such an assumption since otherwise every cone should sort its rays during construction (and it is not really even "sorting", it is just selecting a certain subset and putting it in front) and cones of fans will not be able to have the order of rays induced from the fan. On the other hand, it is easy to get basis as something like

self.rays(self.ray_matrix().pivots())

(I didn't check the exact command, but it is possible to get indices of pivot columns).

2) (very minor) Maybe is_origin is more intuitive than is_trivial? I am fine with both names, just a thought. And probably this function should be added to IntegralRayCollection, so that it is available for fans as well. Such little functions were exactly the reason for creating that class.

3) I am against functions and attributes with direct names of lattices. I want to be able to have cones in any lattice and call any functions on them. If lattice names are hard-coded into functions it makes it confusing to call them for cones from the dual lattice. I agree that N and M are standard, but in mirror symmetry it is also common to perform operations on both sides and it would be better if it was possible to do it without making a representative of each fan in the N-lattice.

4) It seems that some suffix like _basis would be nice for functions that return not the actual lattice in the sense of a ToricLattice object, but rather a sequence of elements that generate it.

5) Related to 4), but perhaps a note for the future todo list rather than something to be implemented in this patch. Ideally, I think all these methods should return ToricLattice objects with canonical coercion maps between appropriate lattices. I don't know how easy it will be to implement it, but it seems it should be more natural and convenient if it works. As I understand, tests like belonging to a lattice will then work not only for the actual lattice elements, but also for elements from those related lattices directly. I can try to play with it in a week, once I am home. By the way, if 4) is done now, then 5) can be done later without any name conflicts by adding functions without prefix.

Let me know what you think!

Andrey

[vbraun]

comment:3

1) Oops, yes will fix this (probably tomorrow)

2) I think "trivial cone" is standard nomenclature. But I'll have to say I was a bit confused as to how to split methods between Cone and IntegralRayCollection, and just put is_trivial together with all the other is_* methods. But I guess everything that does not reference ambient should go into IntegralRayCollection. Then, for example, is_simplicial should be moved as well?

3) The lattice will always be the cone.lattice() one. I agree that it might be confusing if the lattice is called MyNLattice yet the method is still called cone.N() and not cone.MyNLattice(). On the other hand, writing sigma.N() for N_\sigma is extremely cute. I would claim that most beginners will end up using the default N/M lattices, and to advanced users it will be clear that the method names don't change just because you change the lattice name. Of course I'm open to better names...

4,5) If I remember correctly then the "sequence of generating lattice vectors" ends up being used more often than the projection to the quotient lattice. So you might want to wait a bit before overengineering this part.

[vbraun]

Author: Volker Braun

[vbraun]

comment:4

The new patch fixes the ray_basis() and moves various methods that don't depend on ambient from ConvexRationalPolyhedralCone to its base class IntegralRayCollection.

[vbraun]

Reviewer: Andrey Novoseltsev

[vbraun]

Attachment: trac_9296_lattice_computations_for_cones.patch.gz

Updated patch

[novoselt]

comment:5

2) is_trivial it is then!

All methods that go into IntegralRayCollection should make sense AND have the same implementation for cones and fans. Mostly things like ray/rays/ray_matrix/lattice.

is_simplicial makes sense for cones and fans but has different code and definition, so such functions must be placed separately into cone and fan classes. I am pretty sure that I already put everything possible into ray collection class - I didn't plan it at all initially, but then got annoyed repeating ray accessing methods. Please return back the moved methods ;-) Things like containment checks are definitely different for cones and fans. Things like lines don't seem to make any sense for fans, so should not appear as valid methods.

3) I would interpret sigma.N() more like N(sigma) rather than N_sigma. As I understand both notations are in use to denote complementary things and it does not add clarity.

Perhaps a solution is to use names like spanned_lattice, complementary_lattice etc. (I just made up these names, so they probably deserve some further thinking/choosing), and make an option to add synonyms. E.g. there is some way in Sage to turn on creation of names automatically and to allow function-like syntax instead of methods. We can have a function like beginner_mode in toric modules (probably fan is the best place to put it, to allow simultaneous changes to cones and fans in the same place), which will do things like

...
ConvexRationalPolyhedralCone.N = ConvexRationalPolyhedralCone.spanned_lattice
...

What do you think about it? If the name sounds too patronizing, we can choose something like use_M_and_N_toric_lattices. I do not want to have it by default, but as an option it gives the system more flexibility and makes it better.

4,5) If I remember correctly then the "sequence of generating lattice vectors" ends up being used more often than the projection to the quotient lattice. So you might want to wait a bit before overengineering this part.

Absolutely, the only change in this direction that I would like to get in this patch are names more accurately representing what do they actually return. If they return a basis of something, then something_basis is more clear than just something. A side effect of this is that if we need to add something method later, it will be easy, but there is no necessity for this addition. I regret that points method of lattice polytopes returns a matrix, a list of points would be more convenient. If I had named this method point_matrix to start with, not only it would be more clear, but it would be trivial to add points method returning a list now.

[vbraun]

comment:6

2) I think is_trivial then belongs to ConvexRationalPolyhedralCone (where I put it originally). The meaning of "trivial fan" usually depends on the context.

3) I see your point, but

• Since there is a N_basis and N_quotient it should be clear that the first is N_\sigma and the second is N(\sigma) in the standard notation. And yes, the standard notation has its quirks, but I think we should adhere to it.
• once you start with sigma.spanned_latttice() you should write sigma.spanned_lattice_perpendicular_basis() for M(\sigma). Too long for my taste.
• none of the lattice computations are particularly useful for beginners, they will usually be used by other methods to compute geometric quantities.
• multiple interfaces for the same quantity would be against the python spirit.

4,5) Makes sense, I added the _basis suffix where appropriate.

[vbraun]

Attachment: trac_9296_lattice_computations_for_cones.2.patch.gz

Updated patch

[vbraun]

Attachment: trac_9296_lattice_computations_for_cones.3.patch.gz

Documentation linking fixes

[novoselt]

comment:7

3) I think the best resolution here will be to get opinions from other people, ideally more than one... I'll start a thread on sage-devel if it works again for me, I had problems last couple of days.

Some more little comments (I am willing to give a positive review even if they are left as is):

• Is there a reason why do you want to return a list in ray_basis instead of a tuple? (self.rays(indices) will give the same vectors as the last line there, but as a tuple instead of a list) Do you think that this basis may be required frequently? I.e. is there any point in caching it? (In which case it probably should be a tuple to avoid accidental changes). Also, it may make sense to actually use IntegralRayCollection for bases, since it will allow easy switch between different representations (e.g. matrix, which is now done by ray_basis_matrix).

• Why does is_trivial documentation mention fans? I mean, there is nothing wrong in what is written there, I don't understand why it is there. I also try to have each docstring start with a one-line description if at all possible. I believe it is somewhere in Python coding guidelines, or maybe even Sage ones.

• INPUT/OUTPUT blocks are formatted differently from guidelines here http://sagemath.org/doc/developer/conventions.html#documentation-strings (although I have to admit that I also don't quite follow it in terms of default values, because it does not always feel natural).

• I think that the plan is to eventually require INPUT/OUTPUT blocks in every function, unless there is no input and/or output at all. So it may be a good idea to add OUTPUT to things like is_trivial, even though the documentation already does describe the output.

• Can we use point instead of n in functions like N_projection? I don't quite associate n with an element of a lattice (especially when the lattice is not called N) and since it is an input parameter, it would be nice to have it more descriptive.

[novoselt]

comment:8

Started discussion about names: http://groups.google.com/group/sage-devel/browse_thread/thread/9731aab9f2258e98

[vbraun]

comment:9

• made ray_basis caching and return a tuple

• changed is_trivial documentation

• improved INPUT/OUTPUT blocks

• changed argument n to point.

[vbraun]

Attachment: trac_9296_lattice_computations_for_cones.4.patch.gz

misc fixes

[novoselt]

comment:10

Wonderful! I guess names for lattice functions are pretty much the last issue.

There is a typo in the documentation of OUTPUT for is_trivial - it says the opposite of what the function does. (The function itself and examples are correct.)

Feel free to add yourself to the copyright section of the module.

In the AUTHORS section, how about expanding your line a little bit? Say "- Volker Braun (2010-06-21): spanned/quotient lattice computations added."

[novoselt]

comment:11

Despite of our recent discussion on #8989, here I am still in favour of long descriptive names ;-)

However I think that it will be very nice to add toric_M_N_lattices function or something like this (starting with toric_) in the global name space. When invoked, it will add to the global name space functions N, N_, M, and M_, overriding the standard N which we definitely should not change by default. These functions can behave like this:

• N(sigma) gives exactly what it looks like;
• N_(sigma) gives N_sigma;
• N(stuff) where stuff is not a cone, tries to convert it into an element of the N-lattice of the appropriate dimension;
• M works similarly.

What do you think of this? I can write an appropriate patch and put it either here or in a separate ticket.

[vbraun]

long-style names

[vbraun]

comment:12

Attachment: trac_9296_lattice_computations_for_cones.5.patch.gz

In the patch above I renamed the methods

• N_basis -> sublattice_basis
• N_projection -> sublattice_projection
• N_complement_basis -> sublattice_complement_basis
• N_quotient_basis -> sublattice_quotient_basis
• M_basis -> perpendicular_sublattice_basis
• M_quotient_basis -> perpendicular_quotient_basis and rewrote the documentation.

I dediced on sublattice instead of spanned_lattice because its shorter and differentiates better the already-existing method lattice() (which returns the ambient lattice). Let me know what you think...

I'm not sure if the lattice computations are a used often enough "by hand" to warrant the additional toric_M_N_lattices interface. Since we can add that always later its not a big priority for me right now.

[novoselt]

comment:13

Personal taste: I like "orthogonal" more than "perpendicular" and it is a little shorter.

I would like to have internal names in agreement with public ones, it makes it easier to read/modify and helps to avoid bugs, e.g. the following code looks strange:

def sublattice_basis(self): 
    ...
    if "_sublattice_basis" not in self.__dict__: 
        self._compute_N_and_N_complement() 
    return tuple( self._lattice(n) for n in self._N.rows() ) 

In general I think that the best name for caching the result of function f is _f, unless it leads to any conflicts. If you don't want to have too long names in the code, I think abbreviations are fine, as long as they still clearly relate to the original name, e.g. perpendicular_sublattice_basis can be cached in something like _perp_sublat_b.

How about also _compute_N_and_N_complement ===> _split_ambient_lattice or something like this?

[vbraun]

Names changed as per Andrey's comment.

[novoselt]

comment:14

Attachment: trac_9296_lattice_computations_for_cones.6.patch.gz

After more careful reading of the code and the documentation, I am having second thoughts about the importance of 5) in the first comments - returning ToricLattice objects as sublattice etc.

Basically, we have two dual lattices and want to decompose each of them into two. After that it seems that there is need to access "embedded" basis of each sublattice, matrix of this basis, and work with projections that will be given as elements in a lower dimensional lattice. If each of the four sublattices is an instance of some ToricSublattice (analog of (ZZ^3).submodule(...)), then there should be only four methods in cones to access them and every single one will have exactly the same methods for basis, basis matrix, and projection. This will be more clear and consistent and will help to avoid code duplication and extremely long names.

Right now I find it confusing for a programmer (at least for me) that sublattice_basis and _sublattice_basis are, in principle, the same things, but represented quite differently. I also find it confusing for a user that sublattice_basis works with sublattice in the embedded representation and sublattice_projection in quotient. I also don't quite like the lattice argument to projection functions - it seems to me that all lattices in question should be fixed once they are constructed the first time, since they are closely related to each other and are completely determined by the cone itself and the chosen way of splitting. (It does make sense, however, to have these lattices "incompatible" for different cones, but given the way how they work now it is not that easy to create them.)

Sorry for dragging so long a relatively simple ticket, but I seems to me that there are two ways to total happiness:

• Implement ToricSublattice class and use it.

• Make these methods private untill there is ToricSublattice class.

Let me know what you think...

[vbraun]

comment:15

Right now xxx_basis() methods return sublattices in the "embedded representation" and the xxx_projection() method in the "quotient representation". In practice, the embedded representation is the one you usually want. I needed the projection only for the orbit closure (i.e. the usual star of a cone as a projection on a complement of the lattice spanned by the given cone).

How are you going to specify names for the quotient lattice if not by passing it as an (optional) argument to the projection method?

Note that you'll also need sublattices of sublattices if you want to introduce an extra sublattice class. However, for example for the Chow group computation that is all overkill and you only need (an arbitrary but fixed choice of) generators of the embedded sublattice.

[novoselt]

comment:16

Actually, I have just tried the following:

sage: N = ToricLattice(3)
sage: Ns = N.submodule([(1,1,0), (-1,1,0)])
sage: Ns
Free module of degree 3 and rank 2 over Integer Ring
Echelon basis matrix:
[1 1 0]
[0 2 0]
sage: Ns.ambient_module()
3-d lattice N
sage: Ns.ambient_vector_space()
Vector space of dimension 3 over Rational Field
sage: Ns.basis()
[
(1, 1, 0),
(0, 2, 0)
]
sage: N.basis()
[
N(1, 0, 0),
N(0, 1, 0),
N(0, 0, 1)
]
sage: Ns.basis_matrix()
[1 1 0]
[0 2 0]
sage: type(Ns)
<class 'sage.modules.free_module.FreeModule_submodule_pid_with_category'>
sage: Ns.coordinates((2,4,0))
[2, 1]
sage: Ns.linear_combination_of_basis([2,1])
(2, 4, 0)

So it seems to me that submodules already work quite good for the purposes of N_\sigma and N(\sigma), the only things that have to be addressed are _repr_ and using toric lattice elements instead of generic vectors. It is also possible to construct submodules of submodules, so there is no problem there.

For quotients more care is necessary since in general they are not lattices. Perhaps a derived class can intercept the quotient method, construct a toric lattice if it is possible, and use the general framework otherwise, leaving toric category. There is no good defaul way to name the quotient lattice, so there should be a way to give this name somehow, but I think that is should be fixed once given. Maybe something like this should work:

sage: cone = ...
sage: Q = cone.sublattice_quotient("Q")
sage: Q = cone.sublattice_quotient("R")
...
ValueError: cannot rename the quotient by sublattice complement!
sage: Q.projection()

where Q is constructed as cone.lattice().quotient(cone.sublattice_complement(), name="Q").

[novoselt]

comment:17

I have rewritten ToricLattice to completely mimic all classes of FreeModule_over_pid, so far everything works and didn't require any adjustments to other modules, which is good. Will add sublattice/quotient lattices and post a patch today or tomorrow. Are you OK with these names:

• submodule to construct a sublattice (that is the inherited name, so the question is basically should there be sublattice alias or not);

• quotient (same as / operator) to get the usual quotient which can contain torsion;

• quotient_lattice(sublattice, <target_specification>) to construct the quotient by sublattice (raise exception if it is not saturated) as a toric lattice with possible specification of what the result should be. If we want to use lift, it maybe necessary to add another class.

[vbraun]

comment:18

I'm fine with the names, but submodules of FreeModule echelonizes the base:

sage: L = FreeModule(ZZ, 3)
sage: Lsub = L.submodule( [[1,1,2],[4,3,2]] );
sage: Lsub.gens()
((1, 0, -4), (0, 1, 6))

For toric purposes, we need generators to lie in the "positive half-space" (as defined by the cone spanning the sublattice) for one-dimensional sublattices.

[novoselt]

comment:19

It is the default behaviour, but it is possible to provide your own basis and enforce using it instead of the echelonized one.

[novoselt]

comment:20

Opened #9504 with a partial patch (needs more documentation and quotients, but submodules with specified bases should work). Couldn't finish it today since #9502 unexpectedly appeared and took longer than expected. Volker, thank you so much for insisting on printing "N" for toric lattice elements, it is not the first time when this feature helped me to catch bugs!

[novoselt]

Work Issues: switch to using sublattices (#9504)

[novoselt]

Description changed:

--- 
+++ 
@@ -6,4 +6,5 @@
 - #8986 - Add support for convex rational polyhedral cones
 - #9188 - lattice_polytope.facet_normal bug with polytopes of less that full dimension
 - #8987 - Add support for rational polyhedral fans
+- #9504 - Add support for toric sublattices

[vbraun]

comment:21

I've changed the method names (yet again) to:

• sublattice()
• sublattice_quotient(point=None)
• sublattice_complement()
• orthogonal_sublattice()
• relative_quotient(subcone)
• relative_orthogonal_quotient(supercone) Now we always return toric sublattices / quotient lattices. The current interface is actually pretty nice, thanks to Andrey's work!

[vbraun]

Attachment: trac_9296_lattice_computations_for_cones.7.patch.gz

switch to toric sub/quotient lattices instead of handing around bases

[vbraun]

Description changed:

--- 
+++ 
@@ -1,10 +1,6 @@
 Various computations in toric geometry rely on the (saturated) N-sublattice generated by a cone and its complement and projections onto these. And, similarly, for the dual cones in the M-lattice. This patch adds what is necessary for Chow group and sheaf cohomology computations later on.

-Prerequisites:

-- #9062 - Add support for toric lattices
-- #8986 - Add support for convex rational polyhedral cones
-- #9188 - lattice_polytope.facet_normal bug with polytopes of less that full dimension
-- #8987 - Add support for rational polyhedral fans
-- #9504 - Add support for toric sublattices
+See tracker bug at #9604 to for the patch queue/dependencies.

+

[vbraun]

Attachment: trac_9296_lattice_computations_for_cones.8.patch.gz

Updated patch for changes in ToricLattice_quotient

[novoselt]

comment:23

I fixed some typos and broke very long lines in doctests (such things make the documentation look a bit weird when it is shown in narrow windows).

I also think that optional point argument should be removed from sublattice_quotient since in the new framework cone.sublattice_quotient(p) is equivalent to cone.sublattice_quotient()(p) and while the second variant does not look quite as nice it has the advantage of always using the same constructor for elements with different forms of input which are documented in a single place. For example, it is possible to write

sage: c = Cone([(1,0)])
sage: c.sublattice_quotient()(0)
N[0, 0]
sage: c.sublattice_quotient()(0,1)
N[0, 1]
sage: c.sublattice_quotient()([0,1])
N[0, 1]

but

sage: c.sublattice_quotient(0,1)
...
TypeError: sublattice_quotient() takes at most 2 arguments (3 given)

It will also make all cone-lattice methods more uniform in their behaviour (i.e. they don't take any arguments). In fact, by the end of writing this I got so convinced that this is the way to go that my patch will do the proposed change ;-) It may affect the subsequent patches, if this functionality was used already, but corrections will be trivial.

If you are fine with the changes, this ticket finally gets positive review!!!

[novoselt]

Changed work issues from switch to using sublattices (#9504) to none

[novoselt]

comment:24

On the other hand, there is a clean way to get consistency and avoid extra parenthesis. Working on it, will update the reviewer patch!

[novoselt]

comment:25

Attachment: trac_9296_reviewer.patch.gz

In addition to other changes, in the new version all arguments to cone related lattices are passed to these lattices, so it is possible to write

sage: sage: c = Cone([(1,0)])
sage: sage: c.sublattice_quotient(0,1)
N[0, 1]

etc. and it will mean exactly the same as

sage: sage: c = Cone([(1,0)])
sage: sage: c.sublattice_quotient()(0,1)
N[0, 1]

This is done for all sub-/quotient lattice functions except for "relative" ones since for those, I think, it is more natural not to mix cone and point arguments. The documentation does not describe what exactly can be passed to these functions, it is just "something that defines an element", so those who do need description will have to get a lattice and then check how its elements are constructed.

[vbraun]

comment:26

Looks good! I, too, prefer <=80 chars per line for the docstrings, I just didn't know that you can linebreak the sage output and still pass the doctests.

[novoselt]

comment:27

Replying to @vbraun:

Looks good! I, too, prefer <=80 chars per line for the docstrings, I just didn't know that you can linebreak the sage output and still pass the doctests.

As I understand, doctests are sensitive to whitespace, but you can break lines at any space. I am not sure if there is any official description of this feature somewhere, but it is certainly useful for complicated objects. Positive review!

[e14f4152-4982-4ace-8c95-73a0599b109b]

Merged: sage-4.6.alpha1