Implementing Wells' Algorithm

[sagetrac-rlmiller]

Implementing Wells' Algorithm for GSOC 2017. A faster way to solve for canonical height in QQ and ZZ because you don't need to factor the resultant.
This algorithm is found in Elliot Wells' Paper "Computing the Canonical Height of a Point in Projective Space"

Component: dynamics

Keywords: gsoc2017

Author: Rebecca Lauren Miller, Paul Fili

Branch/Commit: 47c1957

Reviewer: Ben Hutz

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

[sagetrac-rlmiller]

Branch: u/rlmiller/wells

[sagetrac-rlmiller]

Commit: d9e145d

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3c128bb

23334 updates, added error bound

[sagetrac-git]

Changed commit from d9e145d to 3c128bb

[pfili]

Changed branch from u/rlmiller/wells to u/paulfili/wells

[sagetrac-rlmiller]

Changed branch from u/paulfili/wells to u/rlmiller/wells

[sagetrac-rlmiller]

Author: Rebecca Lauren Miller, Paul Fili

[sagetrac-rlmiller]

comment:8

Fixed test errors so we are ready to review. Wondering if we should take out a new ticket so we can change all the prec to 53.

[sagetrac-rlmiller]

Changed commit from 3c128bb to 6a14427

[fchapoton]

comment:9

doc does not build:

+[dochtml] OSError: [schemes  ] /local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage/schemes/projective/projective_point.py:
docstring of sage.schemes.projective.projective_point.SchemeMorphism_point_projective_ring.canonical_height:39:
 WARNING: Explicit markup ends without a blank line; unexpected unindent.

[bhutz]

comment:10

A took a first look and here are a few initial comments:

• also change the description of the algorithm in canonical_height in projective_morphism

• move reference to reference file and add citations here

• 1031: line too long

• a bunch of your earlier work is to get integer coefficients and coordinates. I'd recommend using the built in functions instead

  • f.normalize_coordinates() - removes gcd and clears denominators
  • Q.normalize_coordinates() - removes gcd
  • Q.clear_denominators() - clears denominators

• 'not err == None' should be 'not err is None'

• Height_I - lower case

• you do a lot of extraneous variable assignment for example

  • P = self
  • f = F
  • A_0, B_0

you don't need all these extra variables floating around

• and something not minor: The error bound calculation seems to be failing. I put in Wells example 4.4 as a test (which I recommend you do as well) and got the appropriate value when assigning N but not when assigning err.

RSA768 = 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
P.<x,y>=ProjectiveSpace(QQ,1)
H=End(P)
f=H([RSA768*x^2+y^2,x*y])
Q=P(RSA768,1)
Q.canonical_height(f, err=0.00000000000000001)
930.66293109982349403319550850
Q.canonical_height(f, N=50)
931.18256422718194018675677246

same was true for simple functions as well.

[bhutz]

Reviewer: Ben Hutz

[bhutz]

Changed keywords from GSOC to gsoc2017

[fchapoton]

comment:20

doc still does not build :

sage.schemes.projective.projective_point.SchemeMorphism_point_projective_ring.canonical_height:79: WARNING: Literal block expected; none found.

probably because of the RSA768 line

Note that in the same function, you should not indent the content of the ALGORITHM section.

EDIT:

Something else: in the reference file, the link to arxiv should be written

:arxiv:`1602.04920v1`

[bhutz]

comment:21

also when you combined 1157,1158 you left in the redundant term (you are both adding and subtracting this term)

R(self[1].abs()).log()

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

684b599

23334 fixed documentaion

[sagetrac-git]

Changed commit from 402a906 to 684b599

[fchapoton]

comment:24

Several typos here:

Looks diffrent than Well's Algorithm because of the diffrence
...
for the infite place

Also range(0, N) should be range(N)

This

+            h = self.green_function(F, 0 , **kwds) - H + R(t).log()
+            return h

can be made in one line (no need to store h)

[sagetrac-git]

Changed commit from 684b599 to 695b96d

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

695b96d

23334 fixed typos and cleaned up code

[bhutz]

comment:26

docs build and all tests pass. I this is ready.

[sagetrac-rlmiller]

comment:28

Need to make sure all "Wells'", are in the correct form. Just quick typo fixes.

[sagetrac-git]

Changed commit from 695b96d to 47c1957

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

47c1957

23334 fixed to Wells'

[vbraun]

Changed branch from u/rlmiller/wells to 47c1957