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 )
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)
Change History (20)
comment:1 Changed 9 years ago by
- Description modified (diff)
Changed 9 years ago by
comment:2 Changed 9 years ago by
- Cc novoselt added
- Description modified (diff)
- Status changed from new to needs_review
comment:3 Changed 9 years ago by
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
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
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
- Dependencies set to #12544
- Reviewers set to Andrey Novoseltsev
comment:7 follow-up: ↓ 9 Changed 9 years ago by
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: ↓ 10 Changed 9 years ago by
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
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
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
- Description modified (diff)
Tests pass now. The first patch is OK modulo changes, going through others...
Changed 8 years ago by
comment:12 Changed 8 years ago by
- 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
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.
comment:14 Changed 8 years ago by
- 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
- Merged in set to sage-5.3.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
Updated patch