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: |
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 6 years ago by
Owner: | set to rlmiller |
---|
comment:2 Changed 6 years ago by
Branch: | → u/rlmiller/wells |
---|
comment:3 Changed 6 years ago by
Commit: | → d9e145d44c3e2e18e00409ff93620d4bee6141a2 |
---|---|
Component: | PLEASE CHANGE → algebra |
Priority: | major → minor |
Status: | new → needs_info |
comment:4 Changed 6 years ago by
Component: | algebra → algebraic geometry |
---|---|
Description: | modified (diff) |
comment:5 Changed 6 years ago by
Commit: | d9e145d44c3e2e18e00409ff93620d4bee6141a2 → 3c128bbb7de8c329528c168e49748f7a38b2f23f |
---|
comment:6 Changed 6 years ago by
Branch: | u/rlmiller/wells → u/paulfili/wells |
---|
comment:7 Changed 6 years ago by
Branch: | u/paulfili/wells → u/rlmiller/wells |
---|
comment:8 Changed 6 years ago by
Authors: | → Rebecca Lauren Miller, Paul Fili |
---|---|
Commit: | 3c128bbb7de8c329528c168e49748f7a38b2f23f → 6a14427ebd9cc17ae6a6ee46bec343339b4f41ff |
Description: | modified (diff) |
Status: | needs_info → 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 6 years ago by
Status: | needs_review → needs_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
Cc: | paulfili bhutz removed |
---|---|
Keywords: | gsoc2017 added; GSOC removed |
Milestone: | sage-8.0 → sage-8.1 |
Reviewers: | → Ben Hutz |
Type: | PLEASE CHANGE → 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 6 years ago by
never mind about the error bound issue. When I use the correct parameter it works as expected.
comment:12 Changed 6 years ago by
Commit: | 6a14427ebd9cc17ae6a6ee46bec343339b4f41ff → 09692fa7d2f81ee8b0956af6fd6719bc278a1c8c |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
09692fa | 22334 simplified code, added example
|
comment:13 Changed 6 years ago by
Branch: | u/rlmiller/wells → u/paulfili/wells |
---|
comment:14 Changed 6 years ago by
Commit: | 09692fa7d2f81ee8b0956af6fd6719bc278a1c8c → c525086e4ef31baafec5acf8aa54f405dfb06798 |
---|---|
Status: | needs_work → 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 6 years ago by
Status: | needs_review → 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(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
Branch: | u/paulfili/wells → u/rlmiller/wells |
---|
comment:17 Changed 6 years ago by
Commit: | c525086e4ef31baafec5acf8aa54f405dfb06798 → 06a23c175d9588304b11838b8358580209bf315e |
---|---|
Status: | needs_work → 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(d-1).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 6 years ago by
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
Commit: | 06a23c175d9588304b11838b8358580209bf315e → 402a9067eebfcc120c73574f553d3fae38ed787c |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
402a906 | 23334 condensed code and added description
|
comment:20 Changed 6 years ago by
Status: | needs_review → 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 6 years 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 6 years ago by
Commit: | 402a9067eebfcc120c73574f553d3fae38ed787c → 684b5991ad9cfa92340584b258a67c2b39df821c |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
684b599 | 23334 fixed documentaion
|
comment:23 Changed 6 years ago by
Status: | needs_work → needs_review |
---|
comment:24 Changed 6 years 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 6 years ago by
Commit: | 684b5991ad9cfa92340584b258a67c2b39df821c → 695b96dd4605eb4505d8160beef234c3e9d3a4d2 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
695b96d | 23334 fixed typos and cleaned up code
|
comment:26 Changed 6 years ago by
Status: | needs_review → positive_review |
---|
docs build and all tests pass. I this is ready.
comment:27 Changed 6 years ago by
Component: | algebraic geometry → dynamics |
---|
comment:28 Changed 6 years ago by
Status: | positive_review → needs_work |
---|
Need to make sure all "Wells'", are in the correct form. Just quick typo fixes.
comment:29 Changed 6 years ago by
Commit: | 695b96dd4605eb4505d8160beef234c3e9d3a4d2 → 47c1957d4fb30ceea21c84bed0d5f0e6643b68d8 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
47c1957 | 23334 fixed to Wells'
|
comment:30 Changed 6 years ago by
Status: | needs_work → needs_review |
---|
comment:31 Changed 6 years ago by
Description: | modified (diff) |
---|---|
Summary: | Implementing Well's Algorithm → Implementing Wells' Algorithm |
comment:32 Changed 6 years ago by
Status: | needs_review → positive_review |
---|
comment:33 Changed 6 years ago by
Branch: | u/rlmiller/wells → 47c1957d4fb30ceea21c84bed0d5f0e6643b68d8 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Branch pushed to git repo; I updated commit sha1. New commits:
23334 updates, added error bound