Opened 5 years ago

Closed 5 years ago

Last modified 3 years ago

#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 bhutz)

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)

trac15392_referee.patch (5.8 KB) - added by nbruin 5 years ago.
Some suggested improvements
minimal_model.py (14.5 KB) - added by nbruin 5 years ago.
attached file (due to failing patches)
trac_15392_minimal_model.patch (22.4 KB) - added by bhutz 5 years ago.

Download all attachments as: .zip

Change History (36)

comment:1 Changed 5 years ago by bhutz

  • Component changed from PLEASE CHANGE to algebraic geometry

comment:2 Changed 5 years ago by bhutz

  • Status changed from new to needs_review

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.

comment:3 Changed 5 years ago by bhutz

  • Authors set to bhutz

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 vdelecroix

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 bhutz

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 bhutz

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 nbruin

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 be endP1_minimal_model or something more appetizing.
  • phi.is_minimal_model reads a little strange: phi is supposed to be an endomorphism on a P1 (with coordinate choice, i.e., with 0,1,infty marked), not a model of one. Would is_PGL_minimal be better (or perhaps is_minimal)?

Changed 5 years ago by nbruin

Some suggested improvements

comment:8 Changed 5 years ago by nbruin

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 bhutz

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: Changed 5 years ago by bhutz

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.

Changed 5 years ago by nbruin

attached file (due to failing patches)

comment:11 in reply to: ↑ 10 Changed 5 years ago by nbruin

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 bhutz

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 bhutz

apply trac_15392_minimal_model.patch​

comment:14 Changed 5 years ago by nbruin

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.

Last edited 5 years ago by nbruin (previous) (diff)

comment:15 follow-up: Changed 5 years ago by bhutz

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 nbruin

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 bhutz

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 nbruin

  • Authors changed from bhutz to Ben Hutz
  • 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 jdemeyer

  • Status changed from positive_review to needs_info

Please clarify which patch(es) should be merged.

comment:20 Changed 5 years ago by bhutz

  • Description modified (diff)
  • Status changed from needs_info to needs_review

comment:21 Changed 5 years ago by nbruin

  • 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 jdemeyer

  • 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 bhutz

  • 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 jdemeyer

  • 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 bhutz

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 jdemeyer

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 bhutz

comment:27 Changed 5 years ago by bhutz

  • 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 jdemeyer

OK, it works now. Nils, can you do the final review?

comment:29 Changed 5 years ago by jdemeyer

  • Work issues rebase deleted

comment:30 Changed 5 years ago by nbruin

  • Status changed from needs_review to positive_review

How many reviews do we need?

comment:31 Changed 5 years ago by jdemeyer

  • Merged in set to sage-5.13.rc0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:32 Changed 5 years ago by jdemeyer

  • Authors changed from Ben Hutz to Benjamin Hutz

comment:33 Changed 3 years ago by chapoton

  • Authors changed from Benjamin Hutz to Ben Hutz
Note: See TracTickets for help on using tickets.