Opened 9 years ago

Closed 8 years ago

#13189 closed enhancement (fixed)

fan isomorphism check

Reported by: vbraun Owned by: AlexGhitza
Priority: major Milestone: sage-5.3
Component: algebraic geometry Keywords: toric
Cc: novoselt Merged in: sage-5.3.beta2
Authors: Volker Braun Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12544 Stopgaps:

Description (last modified by novoselt)

This patch implements testing for isomorphism (equivalence up to GL(n,ZZ) rotation) of fans

  sage: m1 = matrix([(1, 0), (0, -5), (-3, 4)])
  sage: m2 = matrix([(3, 0), (1, 0), (-2, 1)])
  sage: m1.elementary_divisors() == m2.elementary_divisors() == [1,1,0]
  True
  sage: fan1 = Fan([Cone([m1*vector([23, 14]), m1*vector([   3,100])]), 
  ...               Cone([m1*vector([-1,-14]), m1*vector([-100, -5])])])
  sage: fan2 = Fan([Cone([m2*vector([23, 14]), m2*vector([   3,100])]), 
  ...               Cone([m2*vector([-1,-14]), m2*vector([-100, -5])])])
  sage: fan1.is_isomorphic(fan2)
  True
  sage: fan1.isomorphism(fan2)
  Fan morphism defined by the matrix
  [18  1 -5]
  [ 4  0 -1]
  [ 5  0 -1]
  Domain fan: Rational polyhedral fan in 3-d lattice N
  Codomain fan: Rational polyhedral fan in 3-d lattice N

This is implemented by first computing the isomorphisms of auxiliary labelled graphs, and then trying to lift those to actual fan morphisms.

Apply:

Attachments (5)

trac_13189_Hirzebruch_Jung_continued_fraction.patch (6.4 KB) - added by vbraun 9 years ago.
Updated patch
trac_13189_virtual_rays.patch (6.3 KB) - added by vbraun 9 years ago.
Updated patch
trac_13189_fan_isomorphism.patch (22.6 KB) - added by vbraun 9 years ago.
Updated patch
trac_13189_reviewer.patch (28.1 KB) - added by novoselt 8 years ago.
trac_13189_cone_isomorphism.patch (1.5 KB) - added by vbraun 8 years ago.
Added commit message

Download all attachments as: .zip

Change History (20)

comment:1 Changed 9 years ago by vbraun

  • Description modified (diff)

Changed 9 years ago by vbraun

Updated patch

Changed 9 years ago by vbraun

Updated patch

comment:2 Changed 9 years ago by vbraun

  • Cc novoselt added
  • Description modified (diff)
  • Status changed from new to needs_review

Changed 9 years ago by vbraun

Updated patch

comment:3 Changed 9 years ago by vbraun

Computing the graph automorphism group goes through GAP, which is slow. The updated patch uses a special version of the isomorphism check for 2-d fans which avoids this.

comment:4 Changed 9 years ago by novoselt

I thought Robert Miller wrote a very fast graph automorphism group code for Sage - am I confusing it with something else?

comment:5 Changed 9 years ago by vbraun

There is very nice code to compute one particular graph isomorphism, but I want to iterate over all graph isomorphisms. I'm doing this by combining the chose iso with the automorphisms of one of the graphs. But enumerating the automorphism group is using GAP, presumably you can gain more through group theory than what you can gain by making the graph theory fast.

comment:6 Changed 9 years ago by novoselt

  • Dependencies set to #12544
  • Reviewers set to Andrey Novoseltsev

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

Glanced through, spotted a few typos that I'll fix in the reviewer patch.

What do you mean by the following change of output description??

By default, ``True`` if ``self`` and ``other`` are in the same
`GL(n, \ZZ)`-orbit, ``False`` otherwise.

Do you mind if I also switch computation of the virtual rays to the fan constructor and allow user to specify them? It is convenient e.g. when considering an affine toric variety corresponding to a face of another cone, or a subfanfan with similar structure. Then coordinates on the smaller variety can match the bigger ones.

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

Got one error testing cone.py:

    Traceback (most recent call last):
      File "/home/novoselt/sage-5.2.beta0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/novoselt/sage-5.2.beta0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/novoselt/sage-5.2.beta0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_26[13]>", line 9, in <module>
        frac = Hirzebruch_Jung_continued_fraction_list(k/d)
      File "/home/novoselt/sage-5.2.beta0/local/lib/python/site-packages/sage/rings/arith.py", line 4193, in Hirzebruch_Jung_continued_fraction_list
        if not sage.rings.rational.is_Rational(x):
    AttributeError: 'module' object has no attribute 'is_Rational'

The new module also has to be included into documentation, I think. Is there actually a particular reason why it is not just in fan.py?

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

Replying to novoselt:

What do you mean by the following change of output description??

By default, ``True`` if ``self`` and ``other`` are in the same
`GL(n, \ZZ)`-orbit, ``False`` otherwise.

I'm trying to say that it returns whether the two fans are equivalent up to a GL(n,ZZ) basis change. Apparently not comprehensible enough ;-)

Do you mind if I also switch computation of the virtual rays to the fan constructor and allow user to specify them?

If you want to implement that, go for it.

comment:10 in reply to: ↑ 8 Changed 9 years ago by vbraun

Replying to novoselt:

The new module also has to be included into documentation, I think. Is there actually a particular reason why it is not just in fan.py?

The fan_isomorphism.py file is just a way to prevent fan.py from getting too large. The relevant user-visible documentation is in fan.py, so I don't think we should include fan_isomorphism.py in the developer guide.

comment:11 Changed 9 years ago by novoselt

  • Description modified (diff)

Tests pass now. The first patch is OK modulo changes, going through others...

Changed 8 years ago by novoselt

comment:12 Changed 8 years ago by novoselt

  • Keywords toric added

OK, positive review to Volker's patches modulo reviewer's one, which needs review now.

Changes:

  • move virtual_rays method to fans only and allow specifying them during fan construction;
  • allow addition of point collections, which results in some simplification of code and examples;
  • a bunch of clarification/typo fixes in the documentation.

Also, am I right that with automatically chosen virtual rays the choice cannot affect the isomorphism of cones?

comment:13 Changed 8 years ago by novoselt

For the record: I have removed trailing whitespaces on new lines in the reviewer patch, so I don't think that patchbot should complain. As far as I know, ticket numbers are automatically added, so it should not complain either. And all tests pass, patchbot errors are not related.

Changed 8 years ago by vbraun

Added commit message

comment:14 Changed 8 years ago by vbraun

  • Status changed from needs_review to positive_review

I forgot the commit message in trac_13189_cone_isomorphism.patch, no actual code changes.

The reviewer patch looks good to me.

The virtual ray choice doesn't change whether or not there is a isomorphism of two cones / two fans (barring any bugs), but the matrix entries of the lattice map of course differ.

comment:15 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.3.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.