Opened 3 months ago
Closed 8 weeks ago
#23334 closed enhancement (fixed)
Implementing Wells' Algorithm
Reported by:  rlmiller  Owned by:  rlmiller 

Priority:  minor  Milestone:  sage8.1 
Component:  dynamics  Keywords:  gsoc2017 
Cc:  Merged in:  
Authors:  Rebecca Lauren Miller, Paul Fili  Reviewers:  Ben Hutz 
Report Upstream:  N/A  Work issues:  
Branch:  47c1957 (Commits)  Commit:  47c1957d4fb30ceea21c84bed0d5f0e6643b68d8 
Dependencies:  Stopgaps: 
Description (last modified by )
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"
Change History (33)
comment:1 Changed 3 months ago by
 Owner changed from (none) to rlmiller
comment:2 Changed 3 months ago by
 Branch set to u/rlmiller/wells
comment:3 Changed 3 months ago by
 Commit set to d9e145d44c3e2e18e00409ff93620d4bee6141a2
 Component changed from PLEASE CHANGE to algebra
 Priority changed from major to minor
 Status changed from new to needs_info
comment:4 Changed 3 months ago by
 Component changed from algebra to algebraic geometry
 Description modified (diff)
comment:5 Changed 3 months ago by
 Commit changed from d9e145d44c3e2e18e00409ff93620d4bee6141a2 to 3c128bbb7de8c329528c168e49748f7a38b2f23f
comment:6 Changed 3 months ago by
 Branch changed from u/rlmiller/wells to u/paulfili/wells
comment:7 Changed 3 months ago by
 Branch changed from u/paulfili/wells to u/rlmiller/wells
comment:8 Changed 3 months ago by
 Commit changed from 3c128bbb7de8c329528c168e49748f7a38b2f23f to 6a14427ebd9cc17ae6a6ee46bec343339b4f41ff
 Description modified (diff)
 Status changed from needs_info to needs_review
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.
comment:9 Changed 3 months ago by
 Status changed from needs_review to needs_work
doc does not build:
+[dochtml] OSError: [schemes ] /local/sagepatchbot/sage/local/lib/python2.7/sitepackages/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.
comment:10 Changed 3 months ago by
 Cc paulfili bhutz removed
 Keywords gsoc2017 added; GSOC removed
 Milestone changed from sage8.0 to sage8.1
 Reviewers set to Ben Hutz
 Type changed from PLEASE CHANGE to enhancement
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.
comment:11 Changed 3 months ago by
never mind about the error bound issue. When I use the correct parameter it works as expected.
comment:12 Changed 3 months ago by
 Commit changed from 6a14427ebd9cc17ae6a6ee46bec343339b4f41ff to 09692fa7d2f81ee8b0956af6fd6719bc278a1c8c
Branch pushed to git repo; I updated commit sha1. New commits:
09692fa  22334 simplified code, added example

comment:13 Changed 3 months ago by
 Branch changed from u/rlmiller/wells to u/paulfili/wells
comment:14 Changed 3 months ago by
 Commit changed from 09692fa7d2f81ee8b0956af6fd6719bc278a1c8c to c525086e4ef31baafec5acf8aa54f405dfb06798
 Status changed from needs_work to needs_review
Added requested example and simplified code.
New commits:
c525086  Fixed call to self.clear_denominators() to check that the point is

comment:15 Changed 2 months ago by
 Status changed from needs_review to needs_work
The functionality works fine in tests and the notebook. However, I have a couple minor suggestions and a part I don't understand why it works.
 add citation to projective morphism canonical_height
 shouldn't this part go under ALGORITHM?
If function is defined over ``QQ`` uses Wells Algorithm, which allows us to not have to factor the resultant.
 Does this line really need .abs()?
1154: H = H + R(g).abs().log()/(d**(n+1))
 line 1145 Res.abs() is better than abs(Res)
 Note sure if it is better, but couldn't you do
N = ceil(R(abs(Res)).log().log(d)  R(d1).log(d)  R(err).log(d))
 lines 11578: you really seem to be computing
h = self.green_function(F, 0 , **kwds)  H + R(t).log()
I'm also slightly confused by why this is right. Doesn't Wells' paper (proposition 2.3) have
h = self.global_height()  self.green_function(F,0)  H
I assume that R(t).log() is the correction for the function coordinate normalization.
comment:16 Changed 2 months ago by
 Branch changed from u/paulfili/wells to u/rlmiller/wells
comment:17 Changed 2 months ago by
 Commit changed from c525086e4ef31baafec5acf8aa54f405dfb06798 to 06a23c175d9588304b11838b8358580209bf315e
 Status changed from needs_work to needs_review
The reason our formula looks a bit different is due to the difference between what Wells calls H_infty and what greens function actually returns for the infinite place.
Left * N = ceil(R(abs(Res)).log().log(d)  R(d1).log(d)  R(err).log(d)) as is because that way it will look more like Well's Algorithm.
New commits:
06a23c1  23334 Made updates to code, added reference. Left most as is

comment:18 Changed 2 months ago by
You should still condense those two lines down to one (11578) and perhaps you should add a comment about the difference in notation.
comment:19 Changed 2 months ago by
 Commit changed from 06a23c175d9588304b11838b8358580209bf315e to 402a9067eebfcc120c73574f553d3fae38ed787c
Branch pushed to git repo; I updated commit sha1. New commits:
402a906  23334 condensed code and added description

comment:20 Changed 2 months ago by
 Status changed from needs_review to needs_work
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`
comment:21 Changed 2 months ago by
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()
comment:22 Changed 2 months ago by
 Commit changed from 402a9067eebfcc120c73574f553d3fae38ed787c to 684b5991ad9cfa92340584b258a67c2b39df821c
Branch pushed to git repo; I updated commit sha1. New commits:
684b599  23334 fixed documentaion

comment:23 Changed 2 months ago by
 Status changed from needs_work to needs_review
comment:24 Changed 2 months ago by
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)
comment:25 Changed 2 months ago by
 Commit changed from 684b5991ad9cfa92340584b258a67c2b39df821c to 695b96dd4605eb4505d8160beef234c3e9d3a4d2
Branch pushed to git repo; I updated commit sha1. New commits:
695b96d  23334 fixed typos and cleaned up code

comment:26 Changed 2 months ago by
 Status changed from needs_review to positive_review
docs build and all tests pass. I this is ready.
comment:27 Changed 2 months ago by
 Component changed from algebraic geometry to dynamics
comment:28 Changed 2 months ago by
 Status changed from positive_review to needs_work
Need to make sure all "Wells'", are in the correct form. Just quick typo fixes.
comment:29 Changed 2 months ago by
 Commit changed from 695b96dd4605eb4505d8160beef234c3e9d3a4d2 to 47c1957d4fb30ceea21c84bed0d5f0e6643b68d8
Branch pushed to git repo; I updated commit sha1. New commits:
47c1957  23334 fixed to Wells'

comment:30 Changed 2 months ago by
 Status changed from needs_work to needs_review
comment:31 Changed 2 months ago by
 Description modified (diff)
 Summary changed from Implementing Well's Algorithm to Implementing Wells' Algorithm
comment:32 Changed 2 months ago by
 Status changed from needs_review to positive_review
comment:33 Changed 8 weeks ago by
 Branch changed from u/rlmiller/wells to 47c1957d4fb30ceea21c84bed0d5f0e6643b68d8
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
23334 updates, added error bound