EllipticCurve gens()/gens_certain() caching problem

[Lee Morgenstern]

How do I disable caching for elliptic curve gens() results?

The cache doesn't store (or check) enough information

to return the correct results.

A cache search slows everything down when computing

many different elliptic curves within a programmed loop.

Example:

E = EllipticCurve([-157*157,0])

G = E.gens(descent_second_limit = 13, proof=False)

print len(G), E.gens_certain()

The above takes about 15 seconds to correctly output:

  1 True

But compare that to the following

(after reloading the kernel which clears the cache):

E = EllipticCurve([-157*157,0])

G = E.gens(descent_second_limit = 10, proof=False)

print len(G), E.gens_certain()

H = E.gens(descent_second_limit = 13, proof=False)

print len(H), E.gens_certain()

The above takes less than a second to correctly output

  0 False

and then INSTANTLY outputs the incorrect

  0 False

because it uses an incorrectly cached result.

The descent_second_limit value either wasn't cached

or is ignored for a matching cached gens() call.

The second gens() call shouldn't be matching any

previous result and still take 15 seconds to compute

and then output: 1 True.

The gens() option "use_database=False" has no effect

on this caching operation.

The only way I can clear the cache seems to be

to reload the kernel, but I can't do that within a program.

It would be nice if I could completely disable caching

so that when my program computes many different

elliptic curves in a loop, it wouldn't take longer

and longer to run because sage has to search

for previously matching cached entries which

I know aren't there.  And I think that when there

are too many cached elliptic curves, it stores

them on disk, which takes a thousand times

longer to search.

Running jupyter, sage-7.6.ova, VirtualBox, Windows 10.

Lee

[John Cremona]

Thanks for the report. There are two things here:

1. confusing (or incorrect) caching. Clearly Sage should not blindly
cache returned gens when the descent was unsuccessful (or not proved
to be successful). I think the idea is, though, that if the descent
found some "generators" (independent points of infinite order) then
that information, and the points, are worth keeping, even if it has
not been proved that these points are a complete set of generators
(generating E(Q) up to finite index, or up to torsion).

In your example with the two repeated calls with proof=False, in the
second case you are in effect asking "give me the gens you have cached
tagged with the False flag if possible, otherwise do this computation
and cache the results with the flag set to False". That explains the
behaviour.

The logic of the caching code does try to handle this, by using the
proof parameter (which is None by default). There are (up to) two
different cached lists of points, one from a proof=True computation
and one from a proof=False. If you look at the first few lines of
code with E.gens?? you will see this.

An improvement to this may be possible. The underlying function which
does the work is E._compute_gens() which return points and also
True/False to indicate the status of these. Since computing the
actual generators involves calling code with a large number of
parameters, it is natural for a user to make repeated calls with
increased values of these (at least, the search bound parameters as in
your example) each time, but for this to work as you expect would
require a much more complicated set of caching keys together with code
to work out whether a new set of parameters was weaker or stronger
than any which have been run before. You are welcome to help
implement such a thing!


2. Disabling the cache is not possible without changing the code, but
you can rest it manually for each curve by
E._set_gens([])
and you can see what the cache holds with
E._EllipticCurve_rational_field__gens
(note that these methods start with an underscore to indicate that
they are internal and not normally intended for use by users).

John Cremona

> --
> You received this message because you are subscribed to the Google Groups
> "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-support...@googlegroups.com.
> To post to this group, send email to sage-s...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sage-support.
> For more options, visit https://groups.google.com/d/optout.