Opened 6 years ago

Closed 6 years ago

#23334 closed enhancement (fixed)

Implementing Wells' Algorithm

Reported by: rlmiller Owned by: rlmiller
Priority: minor Milestone: sage-8.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, GitHub, GitLab) Commit: 47c1957d4fb30ceea21c84bed0d5f0e6643b68d8
Dependencies: Stopgaps:

Status badges

Description (last modified by 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"

Change History (33)

comment:1 Changed 6 years ago by rlmiller

Owner: set to rlmiller

comment:2 Changed 6 years ago by rlmiller

Branch: u/rlmiller/wells

comment:3 Changed 6 years ago by rlmiller

Commit: d9e145d44c3e2e18e00409ff93620d4bee6141a2
Component: PLEASE CHANGEalgebra
Priority: majorminor
Status: newneeds_info

comment:4 Changed 6 years ago by rlmiller

Component: algebraalgebraic geometry
Description: modified (diff)

comment:5 Changed 6 years ago by git

Commit: d9e145d44c3e2e18e00409ff93620d4bee6141a23c128bbb7de8c329528c168e49748f7a38b2f23f

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

3c128bb23334 updates, added error bound

comment:6 Changed 6 years ago by paulfili

Branch: u/rlmiller/wellsu/paulfili/wells

comment:7 Changed 6 years ago by rlmiller

Branch: u/paulfili/wellsu/rlmiller/wells

comment:8 Changed 6 years ago by rlmiller

Authors: Rebecca Lauren Miller, Paul Fili
Commit: 3c128bbb7de8c329528c168e49748f7a38b2f23f6a14427ebd9cc17ae6a6ee46bec343339b4f41ff
Description: modified (diff)
Status: needs_infoneeds_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 6 years ago by chapoton

Status: needs_reviewneeds_work

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.

comment:10 Changed 6 years ago by bhutz

Cc: paulfili bhutz removed
Keywords: gsoc2017 added; GSOC removed
Milestone: sage-8.0sage-8.1
Reviewers: Ben Hutz
Type: PLEASE CHANGEenhancement

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 6 years ago by bhutz

never mind about the error bound issue. When I use the correct parameter it works as expected.

comment:12 Changed 6 years ago by git

Commit: 6a14427ebd9cc17ae6a6ee46bec343339b4f41ff09692fa7d2f81ee8b0956af6fd6719bc278a1c8c

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

09692fa22334 simplified code, added example

comment:13 Changed 6 years ago by paulfili

Branch: u/rlmiller/wellsu/paulfili/wells

comment:14 Changed 6 years ago by rlmiller

Commit: 09692fa7d2f81ee8b0956af6fd6719bc278a1c8cc525086e4ef31baafec5acf8aa54f405dfb06798
Status: needs_workneeds_review

Added requested example and simplified code.


New commits:

c525086Fixed call to self.clear_denominators() to check that the point is

comment:15 Changed 6 years ago by bhutz

Status: needs_reviewneeds_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(d-1).log(d) - R(err).log(d))
    
  • lines 1157-8: 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 6 years ago by rlmiller

Branch: u/paulfili/wellsu/rlmiller/wells

comment:17 Changed 6 years ago by rlmiller

Commit: c525086e4ef31baafec5acf8aa54f405dfb0679806a23c175d9588304b11838b8358580209bf315e
Status: needs_workneeds_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(d-1).log(d) - R(err).log(d)) as is because that way it will look more like Well's Algorithm.


New commits:

06a23c123334 Made updates to code, added reference. Left most as is

comment:18 Changed 6 years ago by bhutz

You should still condense those two lines down to one (1157-8) and perhaps you should add a comment about the difference in notation.

comment:19 Changed 6 years ago by git

Commit: 06a23c175d9588304b11838b8358580209bf315e402a9067eebfcc120c73574f553d3fae38ed787c

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

402a90623334 condensed code and added description

comment:20 Changed 6 years ago by chapoton

Status: needs_reviewneeds_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`
Last edited 6 years ago by chapoton (previous) (diff)

comment:21 Changed 6 years ago by bhutz

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 6 years ago by git

Commit: 402a9067eebfcc120c73574f553d3fae38ed787c684b5991ad9cfa92340584b258a67c2b39df821c

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

684b59923334 fixed documentaion

comment:23 Changed 6 years ago by rlmiller

Status: needs_workneeds_review

comment:24 Changed 6 years ago by chapoton

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 6 years ago by git

Commit: 684b5991ad9cfa92340584b258a67c2b39df821c695b96dd4605eb4505d8160beef234c3e9d3a4d2

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

695b96d23334 fixed typos and cleaned up code

comment:26 Changed 6 years ago by bhutz

Status: needs_reviewpositive_review

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

comment:27 Changed 6 years ago by bhutz

Component: algebraic geometrydynamics

comment:28 Changed 6 years ago by rlmiller

Status: positive_reviewneeds_work

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

comment:29 Changed 6 years ago by git

Commit: 695b96dd4605eb4505d8160beef234c3e9d3a4d247c1957d4fb30ceea21c84bed0d5f0e6643b68d8

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

47c195723334 fixed to Wells'

comment:30 Changed 6 years ago by rlmiller

Status: needs_workneeds_review

comment:31 Changed 6 years ago by rlmiller

Description: modified (diff)
Summary: Implementing Well's AlgorithmImplementing Wells' Algorithm

comment:32 Changed 6 years ago by bhutz

Status: needs_reviewpositive_review

comment:33 Changed 6 years ago by vbraun

Branch: u/rlmiller/wells47c1957d4fb30ceea21c84bed0d5f0e6643b68d8
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.