Opened 6 years ago
Closed 6 years ago
#16773 closed enhancement (fixed)
Analytic Rank Bound
Reported by:  spice  Owned by:  spice 

Priority:  major  Milestone:  sage6.8 
Component:  elliptic curves  Keywords:  elliptic curves, analytic rank, lfunctions 
Cc:  Merged in:  
Authors:  Simon Spicer  Reviewers:  William Stein 
Report Upstream:  N/A  Work issues:  
Branch:  7056dd9 (Commits)  Commit:  7056dd9e8dacf3602edc1134b12368017999dd38 
Dependencies:  Stopgaps: 
Description (last modified by )
Implement functionality to bound from above the analytic rank of a rational elliptic curve. This uses the zero sum method as described in http://msp.org/obs/2013/11/obsv1n1p07s.pdf. Because this avoids computing with the curve's Lfunction directly, it is often faster than traditional analytic rank techniques.
The enhancement also includes functionality to compute more general zero sums for an elliptic curve Lfunction, as well as computing with the logarithmic derivative. The elliptic_curves object in Sage has also been modified to contain examples of elliptic curves up to rank 28. To this end the elliptic_curves spkg has been updated to version 0.8. The zipped data file for the spkg can be obtained at http://www.math.washington.edu/~mlungu/files/elliptic_curves0.8.tar.bz2
Complete working sage install with docs built: https://cloud.sagemath.com/projects/8499bab7d4a54956acd2248b5550731d/files/sage/
Built HTML documentation files (as public, this will work later this week, but not now...)
https://cloud.sagemath.com/8499bab7d4a54956acd2248b5550731d/raw/sage/src/doc/output/html/en/reference/lfunctions/sage/lfunctions/zero_sums.html#sage.lfunctions.zero_sums.LFunctionZeroSum https://cloud.sagemath.com/8499bab7d4a54956acd2248b5550731d/raw/sage/src/doc/output/html/en/reference/plane_curves/sage/schemes/elliptic_curves/ell_rational_field.html#sage.schemes.elliptic_curves.ell_rational_field.EllipticCurve_rational_field.analytic_rank_upper_bound
Change History (62)
comment:1 Changed 6 years ago by
 Component changed from PLEASE CHANGE to elliptic curves
 Description modified (diff)
 Keywords elliptic curves analytic rank lfunctions added
 Owner changed from (none) to spice
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 6 years ago by
comment:3 Changed 6 years ago by
 Description modified (diff)
comment:4 Changed 6 years ago by
 Branch set to u/spice/analytic_rank_bound
comment:5 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:6 Changed 6 years ago by
 Commit set to b36d9400d560e5383f88594d136db026e70dd5e5
comment:7 Changed 6 years ago by
I'll be reviewing this. I just read over all of the code and it's in really good shape right now. There are a couple of minor issues that I told Simon about, which he'll address soon.
I have not compiled or run doctests yet.
comment:8 Changed 6 years ago by
 Reviewers set to William Stein
comment:9 Changed 6 years ago by
 Commit changed from b36d9400d560e5383f88594d136db026e70dd5e5 to b12b9dcc76db16fc90d30fed3f7330823bc1455d
Branch pushed to git repo; I updated commit sha1. New commits:
b12b9dc  More documentation, typos, and lseries() interface method

comment:10 Changed 6 years ago by
 Status changed from new to needs_review
comment:11 Changed 6 years ago by
 Commit changed from b12b9dcc76db16fc90d30fed3f7330823bc1455d to 7b4f9d849cf14e709e90880dbdbd5b51b3524b62
Branch pushed to git repo; I updated commit sha1. New commits:
fa4b027  Fixed some documentation errors

f149c97  Cleaning up documentations

5f1f8e4  Preliminary reference manual docs

ae933a4  Merge branch 'gsoc' of https://github.com/haikona/GSoC_2014 into gsoc

f4326a5  Removed prototutorial docs

7b4f9d8  Modified elliptic_curves spkg, major docstring tweaking

comment:12 Changed 6 years ago by
 Description modified (diff)
comment:13 Changed 6 years ago by
 Commit changed from 7b4f9d849cf14e709e90880dbdbd5b51b3524b62 to c7797e5d5c44e467ddebd5586bd48c4b093633f6
comment:14 Changed 6 years ago by
 Description modified (diff)
The elliptic_curves spkg has been updated, and version number incremented to 0.8. The zipped data file for the spkg can be obtained at http://www.math.washington.edu/~mlungu/files/elliptic_curves0.8.tar.bz2
comment:15 Changed 6 years ago by
 Description modified (diff)
comment:16 Changed 6 years ago by
 Description modified (diff)
comment:17 Changed 6 years ago by
 Description modified (diff)
comment:18 Changed 6 years ago by
 Commit changed from c7797e5d5c44e467ddebd5586bd48c4b093633f6 to 663de2318d939f92c47d9cddfd782007fedd17a0
Branch pushed to git repo; I updated commit sha1. New commits:
663de23  Sundry fixes, including removing Numpy import on startup

comment:19 Changed 6 years ago by
 Commit changed from 663de2318d939f92c47d9cddfd782007fedd17a0 to 7d937abb1ec01f1b7f80fe190eab64b18d2803ad
Branch pushed to git repo; I updated commit sha1. New commits:
7d937ab  One more reST docfix

comment:20 Changed 6 years ago by
 Commit changed from 7d937abb1ec01f1b7f80fe190eab64b18d2803ad to ee2f1d954c30f3cc91699281e048a8863aeb7605
comment:21 Changed 6 years ago by
 Commit changed from ee2f1d954c30f3cc91699281e048a8863aeb7605 to c5f7ec9fe7ea604990b7e574fbecf50ac8e2afc6
Branch pushed to git repo; I updated commit sha1. New commits:
c5f7ec9  Docstring indentation fix

comment:22 Changed 6 years ago by
 Commit changed from c5f7ec9fe7ea604990b7e574fbecf50ac8e2afc6 to 4a5f092b8da850e22938e88f1c3b63c754295ba2
Branch pushed to git repo; I updated commit sha1. New commits:
4a5f092  Citation fix

comment:23 Changed 6 years ago by
By curiosity, on which version of sage are you working ? The branch field here above is red, and should rather be green if your commits are to be applied (see any other recent ticket, for example #17255). It is probably better to work on top of the latest development version (now 6.4.rc0).
comment:24 Changed 6 years ago by
I'm working off 6.3. Time to rebase then!
comment:25 Changed 6 years ago by
 Commit changed from 4a5f092b8da850e22938e88f1c3b63c754295ba2 to 07269ec17a7d156b5733b0cb7624bcf049aac950
comment:26 Changed 6 years ago by
Patch has been updated to Sage 6.4.rc1
comment:27 Changed 6 years ago by
 Status changed from needs_review to needs_work
Updating to 6.4.rc1 introduces some minor doctest errors, which I'll need to fix.
comment:28 Changed 6 years ago by
 Commit changed from 07269ec17a7d156b5733b0cb7624bcf049aac950 to 391fa5231aabc117ed95e134ee2089ee290f232d
Branch pushed to git repo; I updated commit sha1. New commits:
391fa52  Fix tests broken by upgrade to Sage 6.4.rc1

comment:29 Changed 6 years ago by
 Commit changed from 391fa5231aabc117ed95e134ee2089ee290f232d to d6871dac899a30e7ca84c9df91b171eea1a63cf5
Branch pushed to git repo; I updated commit sha1. New commits:
d6871da  Merge branch 'master' into gsoc

comment:30 Changed 6 years ago by
 Milestone changed from sage6.4 to sage6.5
 Status changed from needs_work to needs_review
Branch rebased to 6.4.1. All tests pass, so I'm changing the patch to NEEDS_REVIEW.
comment:31 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:32 Changed 6 years ago by
 Status changed from positive_review to needs_work
sage t long warnlong 38.9 src/sage/lfunctions/zero_sums.pyx ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 1333, in sage.lfunctions.zero_sums.LFunctionZeroSum_EllipticCurve.? Failed example: print(E.rank(),Z._zerosum_sincsquared_parallel(Delta=1.5,ncpus=8)) Expected: (0, 0.01047120600865063) Got: (0, 0.010471206008650615) **********************************************************************
comment:33 followup: ↓ 34 Changed 6 years ago by
Also, do you really need 8 cores to test this? Is the code path different from 2 cores?
comment:34 in reply to: ↑ 33 Changed 6 years ago by
Replying to vbraun:
Also, do you really need 8 cores to test this? Is the code path different from 2 cores?
No, the code path is the same either way. I'll change the test to use only 2 cores, and add tolerances (should have done this anyway since the code is doing arithmetic over RDF).
Should I add tolerances to my other numerical tests? Or is this only an issue because I'm using @parallel in this one method?
comment:35 Changed 6 years ago by
You need tolerances wherever the output might have numerical noise. Some floatingpoint operations are guaranteed by IEEE, but e.g. @parallel
will add in random order and floatingpoint addition is not associative.
comment:36 Changed 6 years ago by
 Commit changed from d6871dac899a30e7ca84c9df91b171eea1a63cf5 to 4d5bbec0ebddce3b202d2ab9ff84463ecfdea094
Branch pushed to git repo; I updated commit sha1. New commits:
4d5bbec  Fixed a numerical precision error in a doctest

comment:37 Changed 6 years ago by
 Status changed from needs_work to needs_review
Numerical error in the @parallel method doctest has been fixed, including reducing the number of cores to 2. Patch should be good to go.
comment:38 Changed 6 years ago by
Why the extra print?
sage: print(Z._zerosum_sincsquared_parallel(Delta=1.5,ncpus=2)) sage: Z._zerosum_sincsquared_parallel(Delta=1.5,ncpus=2)
comment:39 Changed 6 years ago by
I split up the output: the numerical value should be an upper bound to the rank of an elliptic curve. The former is a floating point value, however, so there should be an allowed tolerance in the output. I thought that writing the example this way makes the comparison a bit clearer.
comment:41 Changed 6 years ago by
 Status changed from positive_review to needs_work
32bit Linux:
sage t long src/sage/lfunctions/zero_sums.pyx ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 198, in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract.digamma Failed example: Z.digamma(3.2) Expected: 0.9988388912865993 Got: 0.9988388912865995 ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 200, in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract.digamma Failed example: Z.digamma(3.2,include_constant_term=False) Expected: 1.576054556188132 Got: 1.5760545561881325 ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 202, in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract.digamma Failed example: Z.digamma(1+I) Expected: 0.09465032062247625 + 1.076674047468581*I Got: 0.09465032062247693 + 1.076674047468581*I ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 289, in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract.logarithmic_derivative Failed example: Z.logarithmic_derivative(2.2,num_terms=50000) # long time Expected: (0.5751579645060139, 0.008988775519160675) Got: (0.5751579645060141, 0.008988775519160675) ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 305, in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract.logarithmic_derivative Failed example: Z.logarithmic_derivative(complex(3,1)) Expected: (0.04764548578052381 + 0.16513832809989326*I, 6.584671359095225e06) Got: (0.0476454857805238 + 0.16513832809989318*I, 6.584671359095225e06) ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 502, in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract.zerosum Failed example: Z.zerosum(Delta=1,tau=2.876,function="sincsquared") Expected: 1.075551295651154 Got: 1.0755512956511541 ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 504, in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract.zerosum Failed example: Z.zerosum(Delta=1,tau=1.2,function="sincsquared") Expected: 0.10831555377490683 Got: 0.10831555377490693 ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 808, in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract._zerosum_cauchy Failed example: Z._zerosum_cauchy(Delta=1,tau=6.36261389) Expected: 2.180904626331156 Got: 2.1809046263311567 ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 815, in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract._zerosum_cauchy Failed example: Z._zerosum_cauchy(Delta=1,tau=1.5) Expected: 0.9827072037553375 Got: 0.9827072037553374 ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 824, in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract._zerosum_cauchy Failed example: Z._zerosum_cauchy(Delta=1.5) Expected: 12.93835258975716 Got: 12.938352589757159 ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 1180, in sage.lfunctions.zero_sums.LFunctionZeroSum_EllipticCurve._zerosum_sincsquared_fast Failed example: print(E.rank(),Z._zerosum_sincsquared_fast(Delta=1.5)) Expected: (0, 0.0104712060086507) Got: (0, 0.010471206008650728) ********************************************************************** 5 items had failures: 1 of 7 in sage.lfunctions.zero_sums.LFunctionZeroSum_EllipticCurve._zerosum_sincsquared_fast 3 of 10 in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract._zerosum_cauchy 3 of 8 in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract.digamma 2 of 10 in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract.logarithmic_derivative 2 of 10 in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract.zerosum [127 tests, 11 failures, 146.27 s]
comment:42 Changed 6 years ago by
This happens randomly, too:
sage t long src/sage/schemes/elliptic_curves/ell_rational_field.py ********************************************************************** File "src/sage/schemes/elliptic_curves/ell_rational_field.py", line 1665, in sage.schemes.elliptic_curves.ell_rational_field.EllipticCurve_rational_field.? Failed example: Z.analytic_rank_upper_bound(max_Delta=2.8,adaptive=False, # long time root_number="ignore",bad_primes=bad_primes) # long time Exception raised: Traceback (most recent call last): File "/scratch/buildbot/sage/redhawk1/sage_git/build/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 488, in _run self.compile_and_execute(example, compiler, test.globs) File "/scratch/buildbot/sage/redhawk1/sage_git/build/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 850, in compile_and_execute exec(compiled, globs) File "<doctest sage.schemes.elliptic_curves.ell_rational_field.EllipticCurve_rational_field.?[26]>", line 2, in <module> root_number="ignore",bad_primes=bad_primes) # long time File "sage/lfunctions/zero_sums.pyx", line 1728, in sage.lfunctions.zero_sums.LFunctionZeroSum_EllipticCurve.analytic_rank_upper_bound (build/cythonized/sage/lfunctions/zero_sums.c:13597) return run_computation(max_Delta) File "sage/lfunctions/zero_sums.pyx", line 1673, in sage.lfunctions.zero_sums.LFunctionZeroSum_EllipticCurve.analytic_rank_upper_bound.run_computation (build/cythonized/sage/lfunctions/zero_sums.c:12682) bound = self._zerosum_sincsquared_parallel(Delta=Delta, File "sage/lfunctions/zero_sums.pyx", line 1453, in sage.lfunctions.zero_sums.LFunctionZeroSum_EllipticCurve._zerosum_sincsquared_parallel (build/cythonized/sage/lfunctions/zero_sums.c:12269) y += summand[1] TypeError: unsupported operand type(s) for +=: 'float' and 'NoneType' ********************************************************************** 1 item had failures: 1 of 94 in sage.schemes.elliptic_curves.ell_rational_field.EllipticCurve_rational_field.? [815 tests, 1 failure, 216.40 s]
comment:43 Changed 6 years ago by
 Commit changed from 4d5bbec0ebddce3b202d2ab9ff84463ecfdea094 to bbe851c24ed0cf48d1d746bcee4258e7394048ca
Branch pushed to git repo; I updated commit sha1. New commits:
bbe851c  Fix architecture error on numerical doctests

comment:44 Changed 6 years ago by
I adding tolerances to each of the numerical doctests; this should help with the numerical errors that appear when the tests are run on different architecture.
As for that one random error in ell_rational_field.py, I've tracked it to @parallel code being executed when ncpus is large (>8). Given that it seems to run fine on some systems but not others, my guess is that it's probably an issue somewhere in the @parallel framework as opposed to the new code in this patch.
Nevertheless, I've reworked the doctest in any case  a test using that many CPUs is excessive, and it was still taking longer than the suggested ~5 seconds. It now uses smaller parameters and only calls for 2 processors. This should hopefully make it run without issue on any system.
All doctests pass on SMC architecture. I'll also run the full test suite on a different system just to be sure.
comment:45 Changed 6 years ago by
 Can you move
_sum_over_residues
out of the function body and document it
_sum_over_residues
can clearly returnNone
if it falls through the last loop, which is the random error that we get. Can you start with anassert False
(good practice anyways) at the end of it and then try it out with small residue chunks.
 addition is not associative, so parallel reductions always suffer from numerical errors. but
10^10 =~ 10^6 ulp
is ridiculously large.
 doctests are typically run in parallel with one per (virtual) cpu, using @parallel is just slowing it down. Perhaps ncpus should generally return 1 or 2 in
DOCTEST_MODE
 PEP8 whitespace style would be nice, e.g. space after comma
f(a, b, foo=bar)
.
comment:46 Changed 6 years ago by
Hi Volker
Sure, I can enact these changes. Will edit the code appropriately and resubmit in due course.
 Simon
comment:47 Changed 6 years ago by
 Milestone changed from sage6.5 to sage6.8
comment:48 Changed 6 years ago by
 Commit changed from bbe851c24ed0cf48d1d746bcee4258e7394048ca to 5455c8da1c124656fd388800a416e3ebc0d2ba8a
Branch pushed to git repo; I updated commit sha1. New commits:
835572c  Reduced tolerences, moved _get_residue_data() method outside class method

4a4106a  Merge branch 'master' into gsoc

3a36c94  Cleaned up new code in zero_sums.pyx, added _ncpus variable to class

1c59ef8  Merge branch 'develop (6.8beta0)' into gsoc

5455c8d  Fixed whitespace and a couple doctests

comment:49 Changed 6 years ago by
 Status changed from needs_work to needs_review
Patch has been rebased to Sage 6.8beta0, and I've implemented the changes suggested by Volker.
All doctests pass (except one numerical tolerance failure in src/sage/tests/french_book/linsolve_doctest.py, but this has already been pointed out by Rob Beezer in https://groups.google.com/d/msg/sagerelease/QJJLnyGgRs/Agldt9DRHYJ as an SMC architecture issue).
comment:50 Changed 6 years ago by
I have had a quick look, and things seems ok.
One typo : pathalogically
please remove changes to .gitignore
and why not use the existing dilog function ?
comment:51 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:52 Changed 6 years ago by
I just tried to build against sage6.8.beta7 and this fails due to using "flint_depends" in the module_list.py. Evidently flint_depends no longer exists.
comment:53 Changed 6 years ago by
And that this still hasn't got into Sage is depressing.
comment:54 Changed 6 years ago by
Well can we fix the build failure, the typo, and the .gitignore thing? That shouldn't take more than five minutes...
comment:55 followup: ↓ 56 Changed 6 years ago by
 Branch changed from u/spice/analytic_rank_bound to public/ticket/16773
 Commit changed from 5455c8da1c124656fd388800a416e3ebc0d2ba8a to 8ca05d1ad73c40eb744ab727ea9efd8d47cf0615
comment:56 in reply to: ↑ 55 Changed 6 years ago by
 Status changed from needs_work to positive_review
Replying to chapoton:
but still nobody has answered my question about the dilog
Because its not a particularly productive or useful line of inquiry. For general discussions there is sagedevel, if you want to propose some guideline on methods vs functions then open a different ticket. Review should consist of immediately actionable items.
comment:57 Changed 6 years ago by
What ?!
My question was not a matter of "general discussion" but the very precise point that this ticket is reimplementing the dilog function instead of using the existing one. If you think that one should not care for such a code duplication, then of course let us do whatever we want, without boring about explaining why.
comment:58 Changed 6 years ago by
First of all, the ticket does not reimplement the dilog. It uses a library function. The only question is: Should RDF have a convenience .dilog() method next to .sin() etc. The answer to the latter is: I don't give a rat's ass. Its such an inconsequential detail, I want the 5 seconds of my life back that I spent thinking about it. Do you think Sage's success will depend on whether RDF elements have a dilog method? Try to contrast it with the importance of implementing the analytic rank bound.
comment:59 Changed 6 years ago by
 Status changed from positive_review to needs_work
Some more numerical noise on 32bit:
sage t long src/sage/lfunctions/zero_sums.pyx ********************************************************************** File "src/sage/lfunctions/zero_sums.pyx", line 337, in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract.logarithmic_derivative Failed example: Z.logarithmic_derivative(2.2,num_terms=50000) # long time Expected: (0.5751579645060139, 0.008988775519160675) Got: (0.5751579645060141, 0.008988775519160675) ********************************************************************** 1 item had failures: 1 of 10 in sage.lfunctions.zero_sums.LFunctionZeroSum_abstract.logarithmic_derivative [132 tests, 1 failure, 8.98 s] sage t long src/sage/rings/real_double.pyx ********************************************************************** File "src/sage/rings/real_double.pyx", line 2198, in sage.rings.real_double.RealDoubleElement.dilog Failed example: RDF(2).dilog() Expected: 2.46740110027234 Got: 2.4674011002723395 ********************************************************************** 1 item had failures: 1 of 3 in sage.rings.real_double.RealDoubleElement.dilog [423 tests, 1 failure, 0.32 s]
Just needs a suitable # rel tol
...
comment:60 Changed 6 years ago by
 Commit changed from 8ca05d1ad73c40eb744ab727ea9efd8d47cf0615 to 7056dd9e8dacf3602edc1134b12368017999dd38
comment:61 Changed 6 years ago by
 Status changed from needs_work to positive_review
comment:62 Changed 6 years ago by
 Branch changed from public/ticket/16773 to 7056dd9e8dacf3602edc1134b12368017999dd38
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Merge tag '6.3.rc0' of git://github.com/sagemath/sage into gsoc
Fixed docstring typos
Merge branch 'gsoc' of https://github.com/haikona/GSoC_2014 into gsoc
Added parallel functionality for sincsquared zero sum
Cleaning up parallized zero sum code
Replaced PARI primality testing with FLINT primality testing
Generalized _get_residue_data() to arbitrarily large n
Minor documentation typo fixes
Merge branch 'gsoc' of https://github.com/haikona/GSoC_2014 into t/16773/analytic_rank_bound