#15392 closed enhancement (fixed)
Implement minimal model algorithm
Reported by: | bhutz | Owned by: | bhutz |
---|---|---|---|
Priority: | major | Milestone: | sage-5.13 |
Component: | algebraic geometry | Keywords: | sage-days55 |
Cc: | Merged in: | sage-5.13.rc0 | |
Authors: | Ben Hutz | Reviewers: | Nils Bruin |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #14219 | Stopgaps: |
Description (last modified by )
Bruin-Molnar published an algorithm to compute the minimal model of a morphism on P1, "Minimal models for rational functions in a dynamical setting".
Translate their algorithm and code to work with the existing dynamical framework
Apply:
Attachments (3)
Change History (36)
comment:1 Changed 5 years ago by
- Component changed from PLEASE CHANGE to algebraic geometry
comment:2 Changed 5 years ago by
- Status changed from new to needs_review
comment:3 Changed 5 years ago by
forgot to include the GPL in the new file the first time
Brian - can you please add yourself to authors.
comment:4 Changed 5 years ago by
Hello,
It is very good that the code is documented and contains references! But there are several problem with the documentation (see sage developer guide).
1) there are trailing whitespaces
2) the indentation is not good. The blocks INPUT, EXAMPLES must have the same identation as the documentation and you must have a blankline between the block name EXAMPLES and its content (for example lines 201-202 are wrong).
def my_function(arg1, arg2): """ This is a nice function INPUT: - ``arg1`` - a first nice argument - ``arg2`` - an other nice argument EXAMPLES:: sage: my_function(8,3) We can also use the function with strings:: sage: my_function('toto', 'bibi') """
3) Bibliography is not set up properly
4) In the examples (at least) respect the convention "my_variable = f()" and do not use "my_variable=f()". If possible, try to be coherent in function arguments and prefer "def f(a, b=3, c=4)" to "def f(a,b = 3, c=4)".
5) For the name I guess "is_affine_minimal" is more suited than "affine_minimal".
comment:5 Changed 5 years ago by
Yes, 1,2,4 are all simple changes that need to be made. 3 was waiting to add an additional citation (which I have now) and will be fixed as well.
5 I disagree with. The minimalmodel.py file is not exposed to the user, so neither is affine_minimal. The two functions exposed to the user are
is_minimal_model() and minimal_model()
Part of the original citation is that it is enough for minimal to check affine minimal, so those names should be fine.
comment:6 Changed 5 years ago by
Some comments from Alex Molnar:
I ... have finally looked through the code. I only glossed the parts that appear unchanged (with the original code side-by-side) and otherwise think the adaptation to projective morphisms looks good.
Just two minor comments. In line 206, I think you mean vp
to
newvp
, and in line 1453
self
is written
sefl
.
I've updated the patch to make those minor corrections.
comment:7 Changed 5 years ago by
I'm just parking some test code here for my own use:
import urllib Qx.<x>=QQ[] def interpolate(c,n): M=matrix([[c[i]^k for k in range(n+1)]+[-c[i+1]*c[i]^k for k in range(n+1)] for i in range(len(c)-1)]) v=list(M.right_kernel().basis()[0]) return Qx(v[:n+1])/Qx(v[n+1:]) V=[eval(c) for c in urllib.urlopen("http://www.cecm.sfu.ca/~nbruin/intorbits/deg2.txt")] P1.<X,Y>=ProjectiveSpace(QQ,1) def proj_map(f): phi=f(X/Y) return End(P1)([phi.numerator(),phi.denominator()]) [proj_map(interpolate(c,2)((x+1)/(x-1))).is_minimal_model() for c in V[:50]]
I'm noticing it's awfully slow! I think I tried a similar thing with the magma version and that was quite quick. Initial impression is that this is just a sage problem:
ncalls tottime percall cumtime percall filename:lineno(function) 110 0.033 0.000 0.073 0.001 minimal_model.py:41(bCheck) 1847/1843 0.026 0.000 0.031 0.000 polynomial_ring.py:299(_element_constructor_) 26/22 0.022 0.001 0.062 0.003 minimal_model.py:122(blift) 264 0.015 0.000 0.020 0.000 {method 'subs' of 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular' objects} 2097 0.011 0.000 0.015 0.000 {method 'sub' of '_sre.SRE_Pattern' objects} 943 0.010 0.000 0.033 0.000 polynomial_ring_constructor.py:60(PolynomialRing) 3 0.008 0.003 0.169 0.056 minimal_model.py:302(Min) 19104 0.006 0.000 0.006 0.000 {isinstance} 2157 0.004 0.000 0.005 0.000 re.py:226(_compile)
so it looks like just constructing the polynomials is an expensive proposition already. bCheck
does take quite a bit of time by itself too, so there may be some algorithmic issues too. Perhaps we don't care about performance at this point?
(Ah, I see: there are lots of polynomial rings constructed *inside* functions. That shouldn't happen)
Some possible packaging problems:
- I think the file name
sage/schemes/projective/minimal_model.py
will cause problems later on: there are all kinds of projective schemes that have their own concept of minimality, so I think it should beendP1_minimal_model
or something more appetizing. phi.is_minimal_model
reads a little strange:phi
is supposed to be an endomorphism on aP1
(with coordinate choice, i.e., with0,1,infty
marked), not a model of one. Would is_PGL_minimal be better (or perhaps is_minimal)?
comment:8 Changed 5 years ago by
I've attached a "patch" with some suggested improvements. With that version, I was able to check the minimality of [eval(c) for c in urllib.urlopen("http://www.cecm.sfu.ca/~nbruin/intorbits/deg2.txt")]
within a minute (that's a little over 2000 quadratic maps). I'm sure the code could be optimized further, but why bother now? I don't think the current code is doing anything outright silly any more and running %prun
on some examples produces for me a profile I can believe (most time is spent in the recursive blift
, which is what one would expect).
There's still the naming of the file and of the routines to be considered.
The code itself seems fine. I've run it by giving it (known) minimal maps from the tables referred to above, conjugating by random transformations, and seeing if the minimal model returned has the same resultant (up to sign) as the original, and I didn't find problems.
(I noticed there's a doctest failing for blift
now, but that's because the test puts an integer in the input list where there should be polynomials. I propose the doctest gets amended, since the internal use of blift
guarantees that the input consists of a list of polynomials.)
comment:9 Changed 5 years ago by
Those changes look good.
I have thought about the naming and see your point on the file name. Although, I'm inclined to be optimistic for the future and call it endPN_minimal_model
. This will also allow consistent naming for other algorithms for endomorphisms of PN.
I'm also happy to call the function is_PGL_minimal
.
Yes. we should just update the doctest as well as we made our best guess as to what a reasonable test was for the individual functions.
I can fold the patches together and make these changes unless you want to use your referee
patch to do them?
comment:10 follow-up: ↓ 11 Changed 5 years ago by
I went to fold this together and make the other changes, but your patch doesn't apply on my system. Could you double check your patch?
I'm still using 5.12, but it shouldn't matter since these are all changing the new minimal_model.py
anyway.
comment:11 in reply to: ↑ 10 Changed 5 years ago by
Replying to bhutz:
I'm still using 5.12, but it shouldn't matter since these are all changing the new
minimal_model.py
anyway.
OK, back to basics then. You may be aware that sage is in the middle of changing the source control system. I'm working on the git version and have no idea how to get a HG patch out of it (importing hg patches doesn't seem to be a problem) Attached is the file that resulted from my editing. You should be able to get out of that whatever you want by just replacing the file and let your source control system of choice figure out what the changes are.
comment:12 Changed 5 years ago by
Yes, that would certainly do it. In the near future I'll be switching over to git, I just haven't done it yet.
New patch attached with your changes, the names changes, and the doctest fixed.
apply trac_15392_minimal_model.patch
comment:13 Changed 5 years ago by
apply trac_15392_minimal_model.patch
comment:14 Changed 5 years ago by
Looks good to me. Incidentally, the name is_PGL_minimal
might not be the best name. It's certainly descriptive, but the spelling is perhaps a little painful relative to the rest of sage?
Some very small points:
The fact that
sage: phi.minimal_model().resultant()
doesn't work seems a little strange. Shouldn't it be return_conjugation=False
by default, so that the default returns a value that can be immediately used rather than needing unpacking? Also, wouldn't return_transformation
be a better name?
Certainly in the doctest:
sage: f.minimal_model(False)
should refer to the keyword argument by keyword, i.e.,
sage: f.minimal_model(return_transformation=False)
A "positional" false is rather unclear here, even though it works.
Finally (and this is for another ticket): If we're "minimizing" rational transformations, shouldn't we also be "reducing" them, i.e., compute an SL(2,Z) transformation that makes the coefficients small? The most simple approach would be to "reduce" the binary form describing the fixed points or (if that's too degenerate) the points of period n for some small n.
See [Stoll, Michael; Cremona, John E., On the reduction theory of binary forms. J. Reine Angew. Math. 565 (2003), 79–99.], which is fairly easy to implement and which would be useful to have in sage anyway.
comment:15 follow-up: ↓ 16 Changed 5 years ago by
Having the default be False is fine and is now changed.
I do have the two optional parameters as positional that is why it is positional in the doctest. It sounds like you think this should be **kwds
instead of positional. I could change it and don't have a strong opinion either way, but have not done so at this point.
Yes, getting the reduced form would be nice and I'll add it to the dynamics todo list on the wiki.
comment:16 in reply to: ↑ 15 Changed 5 years ago by
Replying to bhutz:
I do have the two optional parameters as positional that is why it is positional in the doctest.
No, in Python, all named arguments can be addressed via keyword. So I wasn't suggesting changing the code, only using the doctest to encourage addressing this option by key. If you prefer, you can still address it by position in your own code. It's just that
phi.minimal_model(True)
isn't very self-documenting.
I think the patch update didn't quite work. Do you want to stick with return_conjugation
rather than return_transformation
?
comment:17 Changed 5 years ago by
ok. That's easy enough to change and is done in this version.
I forgot to qrefresh before, but the correct one should be up.
comment:18 Changed 5 years ago by
- Reviewers set to Nils Bruin
- Status changed from needs_review to positive_review
Good with me. To repeat: I did try the code quite extensively on more or less random examples, where the code has to do non-trivial work and I didn't catch it on any inconsistencies.
comment:19 Changed 5 years ago by
- Status changed from positive_review to needs_info
Please clarify which patch(es) should be merged.
comment:20 Changed 5 years ago by
- Description modified (diff)
- Status changed from needs_info to needs_review
comment:21 Changed 5 years ago by
- Status changed from needs_review to positive_review
Patch hasn't changed, so I don't think "review" is necessary. This is just admin to keep Jeroen's job manageable.
comment:22 Changed 5 years ago by
- Status changed from positive_review to needs_work
- Work issues set to docbuild
dochtml.log:[schemes ] /scratch/release/merger/sage-5.13.rc0/local/lib/python2.7/site-packages/sage/schemes/projective/projective_morphism.py:docstring of sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space.minimal_model:8: WARNING: Duplicate explicit target name: "bruin-molnar". dochtml.log:[schemes ] /scratch/release/merger/sage-5.13.rc0/local/lib/python2.7/site-packages/sage/schemes/projective/projective_morphism.py:docstring of sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space.minimal_model:12: WARNING: Duplicate explicit target name: "molnar". dochtml.log:[schemes ] /scratch/release/merger/sage-5.13.rc0/local/lib/python2.7/site-packages/sage/schemes/projective/projective_morphism.py:docstring of sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space.minimal_model:8: WARNING: duplicate citation Bruin-Molnar, other instance in /scratch/release/merger/sage-5.13.rc0/devel/sage/doc/en/reference/schemes/sage/schemes/projective/projective_morphism.rst dochtml.log:[schemes ] /scratch/release/merger/sage-5.13.rc0/local/lib/python2.7/site-packages/sage/schemes/projective/projective_morphism.py:docstring of sage.schemes.projective.projective_morphism.SchemeMorphism_polynomial_projective_space.minimal_model:12: WARNING: duplicate citation Molnar, other instance in /scratch/release/merger/sage-5.13.rc0/devel/sage/doc/en/reference/schemes/sage/schemes/projective/projective_morphism.rst
comment:23 Changed 5 years ago by
- Status changed from needs_work to needs_review
hmm...Since I using the same references in two different functions it is giving the warning. I'm not 100% sure what the procedure is here. In looking at some of the toric variety code, it seems to be the case to put the reference listing in one place and then use [.]
everywhere else.
So then I've moved the REFERENCES
block to the 'main' function and just used the citation [.]
for the other.
comment:24 Changed 5 years ago by
- Dependencies set to #14219
- Status changed from needs_review to needs_work
- Work issues changed from docbuild to rebase
Please rebase the patch to sage-5.13.beta4 or later.
comment:25 Changed 5 years ago by
Yes, sorry, I should have realized. Even though there is no functionality dependency, they do modify the same file. The new version is rebased.
comment:26 Changed 5 years ago by
sage -t devel/sage/sage/schemes/projective/endPN_minimal_model.py ********************************************************************** File "devel/sage/sage/schemes/projective/endPN_minimal_model.py", line 65, in sage.schemes.projective.endPN_minimal_model.bCheck Failed example: from sage.schemes.projective.minimal_model import bCheck Exception raised: Traceback (most recent call last): File "/scratch/release/merger/sage-5.13.rc0/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 479, in _run self.execute(example, compiled, test.globs) File "/scratch/release/merger/sage-5.13.rc0/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 838, in execute exec compiled in globs File "<doctest sage.schemes.projective.endPN_minimal_model.bCheck[1]>", line 1, in <module> from sage.schemes.projective.minimal_model import bCheck ImportError: No module named minimal_model ********************************************************************** File "devel/sage/sage/schemes/projective/endPN_minimal_model.py", line 66, in sage.schemes.projective.endPN_minimal_model.bCheck Failed example: bCheck(11664*b^2 + 70227*b + 76059, 15/2, 3, b) Exception raised: Traceback (most recent call last): File "/scratch/release/merger/sage-5.13.rc0/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 479, in _run self.execute(example, compiled, test.globs) File "/scratch/release/merger/sage-5.13.rc0/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 838, in execute exec compiled in globs File "<doctest sage.schemes.projective.endPN_minimal_model.bCheck[2]>", line 1, in <module> bCheck(Integer(11664)*b**Integer(2) + Integer(70227)*b + Integer(76059), Integer(15)/Integer(2), Integer(3), b) NameError: name 'bCheck' is not defined **********************************************************************
Changed 5 years ago by
comment:27 Changed 5 years ago by
- Status changed from needs_work to needs_review
ok. I fixed that typo in the test and I've doubled checked that the doctests and the docbuild pass on my system.
comment:28 Changed 5 years ago by
OK, it works now. Nils, can you do the final review?
comment:29 Changed 5 years ago by
- Work issues rebase deleted
comment:30 Changed 5 years ago by
- Status changed from needs_review to positive_review
How many reviews do we need?
comment:31 Changed 5 years ago by
- Merged in set to sage-5.13.rc0
- Resolution set to fixed
- Status changed from positive_review to closed
Working with Brian Stout we've translated Alexander Molnar's minimal model algorithm/code to work within Sage. A few minors changes from his original work, but the algorithm remains unchanged.