Implement minimal model algorithm

[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:

• attachment: trac_15392_minimal_model.patch

Depends on #14219

Component: algebraic geometry

Keywords: sage-days55

Author: Ben Hutz

Reviewer: Nils Bruin

Merged: sage-5.13.rc0

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

[bhutz]

comment:2

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.

[bhutz]

comment:3

forgot to include the GPL in the new file the first time

Brian - can you please add yourself to authors.

[bhutz]

Author: bhutz

[videlec]

comment:4

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".

[bhutz]

comment:5

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.

[bhutz]

comment:6

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.

[nbruin]

comment:7

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)?

[nbruin]

Attachment: trac15392_referee.patch.gz

Some suggested improvements

[nbruin]

comment:8

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.)

[bhutz]

comment:9

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?

[bhutz]

comment:10

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.

[nbruin]

Attachment: minimal_model.py.gz

attached file (due to failing patches)

[nbruin]

comment:11

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.

[bhutz]

comment:12

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​

[bhutz]

comment:13

apply trac_15392_minimal_model.patch​

[nbruin]

comment:14

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.

[bhutz]

comment:15

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.

[nbruin]

comment:16

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?

[bhutz]

comment:17

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.

[nbruin]

comment:18

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.

[nbruin]

Changed author from bhutz to Ben Hutz

[nbruin]

Reviewer: Nils Bruin

[nbruin]

comment:21

Patch hasn't changed, so I don't think "review" is necessary. This is just admin to keep Jeroen's job manageable.

[jdemeyer]

comment:22

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

[jdemeyer]

Work Issues: docbuild

[bhutz]

comment:23

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.

[jdemeyer]

Dependencies: #14219

[jdemeyer]

Changed work issues from docbuild to rebase

[jdemeyer]

comment:24

Please rebase the patch to sage-5.13.beta4 or later.

[bhutz]

comment:25

Yes, sorry, I should have realized. Even though there is no functionality dependency, they do modify the same file. The new version is rebased.

[jdemeyer]

comment:26

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
**********************************************************************

[bhutz]

comment:27

Attachment: trac_15392_minimal_model.patch.gz

ok. I fixed that typo in the test and I've doubled checked that the doctests and the docbuild pass on my system.

[jdemeyer]

comment:28

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

[jdemeyer]

Changed work issues from rebase to none

[nbruin]

comment:30

How many reviews do we need?

[jdemeyer]

Merged: sage-5.13.rc0

[jdemeyer]

Changed author from Ben Hutz to Benjamin Hutz

[fchapoton]

Changed author from Benjamin Hutz to Ben Hutz