Opened 6 years ago
Closed 6 years ago
#16773 closed enhancement (fixed)
Analytic Rank Bound
Reported by: | spice | Owned by: | spice |
---|---|---|---|
Priority: | major | Milestone: | sage-6.8 |
Component: | elliptic curves | Keywords: | elliptic curves, analytic rank, l-functions |
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/1-1/obs-v1-n1-p07-s.pdf. Because this avoids computing with the curve's L-function 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 L-function, 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_curves-0.8.tar.bz2
Complete working sage install with docs built: https://cloud.sagemath.com/projects/8499bab7-d4a5-4956-acd2-248b5550731d/files/sage/
Built HTML documentation files (as public, this will work later this week, but not now...)
https://cloud.sagemath.com/8499bab7-d4a5-4956-acd2-248b5550731d/raw/sage/src/doc/output/html/en/reference/lfunctions/sage/lfunctions/zero_sums.html#sage.lfunctions.zero_sums.LFunctionZeroSum https://cloud.sagemath.com/8499bab7-d4a5-4956-acd2-248b5550731d/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 l-functions 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 sage-6.3 to sage-6.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 proto-tutorial 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_curves-0.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 sage-6.4 to sage-6.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 --warn-long 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 follow-up: ↓ 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 floating-point operations are guaranteed by IEEE, but e.g. @parallel
will add in random order and floating-point 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
32-bit 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.584671359095225e-06) Got: (0.0476454857805238 + 0.16513832809989318*I, 6.584671359095225e-06) ********************************************************************** 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/redhawk-1/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 488, in _run self.compile_and_execute(example, compiler, test.globs) File "/scratch/buildbot/sage/redhawk-1/sage_git/build/local/lib/python2.7/site-packages/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 sage-6.5 to sage-6.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/sage-release/QJJLny-GgRs/Agldt9D-RHYJ 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 sage-6.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 follow-up: ↓ 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 sage-devel, 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 32-bit:
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