Analytic Rank Bound

[spice]

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

[git]

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

​5e7b350	Merge tag '6.3.rc0' of git://github.com/sagemath/sage into gsoc
​0882426	Fixed docstring typos
​f033351	Merge branch 'gsoc' of https://github.com/haikona/GSoC_2014 into gsoc
​33f7b70	Added parallel functionality for sincsquared zero sum
​b72ac10	Cleaning up parallized zero sum code
​6fcb73f	Replaced PARI primality testing with FLINT primality testing
​9fe00d3	Generalized _get_residue_data() to arbitrarily large n
​8585e69	Minor documentation typo fixes
​b36d940	Merge branch 'gsoc' of https://github.com/haikona/GSoC_2014 into t/16773/analytic_rank_bound

[was]

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.

[git]

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

​b12b9dc

More documentation, typos, and lseries() interface method

[git]

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

[git]

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

​5fe05c6	More rEST docstring fixes
​c7797e5	More reST docfixes

[spice]

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

[git]

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

​663de23

Sundry fixes, including removing Numpy import on startup

[git]

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

​7d937ab

One more reST docfix

[git]

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

​edb8b21	Another small reST docfix
​ee2f1d9	reST docfixes continue...

[git]

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

​c5f7ec9

Docstring indentation fix

[git]

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

​4a5f092

Citation fix

[chapoton]

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).

[spice]

I'm working off 6.3. Time to rebase then!

[git]

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

​6fadd0d	Merge to update to Sage 6.4.rc0
​07269ec	Merge branch 'develop' into gsoc

[spice]

Patch has been updated to Sage 6.4.rc1

[spice]

Updating to 6.4.rc1 introduces some minor doctest errors, which I'll need to fix.

[git]

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

​391fa52

Fix tests broken by upgrade to Sage 6.4.rc1

[git]

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

​d6871da

Merge branch 'master' into gsoc

[spice]

Branch rebased to 6.4.1. All tests pass, so I'm changing the patch to NEEDS_REVIEW.

[vbraun]

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)
**********************************************************************

[vbraun]

Also, do you really need 8 cores to test this? Is the code path different from 2 cores?

[spice]

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?

[vbraun]

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.

[git]

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

​4d5bbec

Fixed a numerical precision error in a doctest

[spice]

Numerical error in the @parallel method doctest has been fixed, including reducing the number of cores to 2. Patch should be good to go.

[vbraun]

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)

[spice]

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.

[was]

rubber stamp.

[vbraun]

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]

[vbraun]

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]

[git]

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

​bbe851c

Fix architecture error on numerical doctests

[spice]

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.

[vbraun]

• Can you move _sum_over_residues out of the function body and document it

• _sum_over_residues can clearly return None if it falls through the last loop, which is the random error that we get. Can you start with an assert 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).

[spice]

Hi Volker

Sure, I can enact these changes. Will edit the code appropriately and resubmit in due course.

• Simon

[git]

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

[spice]

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).

[chapoton]

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 ?

[was]

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.

[was]

And that this still hasn't got into Sage is depressing.

[vbraun]

Well can we fix the build failure, the typo, and the .gitignore thing? That shouldn't take more than five minutes...

[chapoton]

done

but still nobody has answered my question about the dilog

---

New commits:

​5fc1a81	Merge branch 'u/spice/analytic_rank_bound' of trac.sagemath.org:sage into 16773
​8ca05d1	trac #16773 remove flint_dep, correct typo and correct gitignore

[vbraun]

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.

[chapoton]

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.

[vbraun]

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.

[vbraun]

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...

[git]

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

​dce6f12	Merge branch 'public/ticket/16773' into 6.8.b8
​7056dd9	trac #16773 adding rel tol in 2 places