Ask Your Question
0

How to define a timeout for EllipticCurve.rank?

asked 2022-04-02 17:17:01 +0200

Daniel Lauer gravatar image

Hello, do you have an idea how to implement a "timeout" for EllipticCurve.rank(only_use_mwrank=True)?

In my application, I have an array of more than 100 elliptic curves and I want to find a subset of 12 curves with rank 0, if possible, in reasonable time. If not possible in reasonable time, I want my function to throw an exception. But it should terminate after let's say 60 seconds.

For most of my elliptic curves the call r = E.rank(only_use_mwrank=True) terminates after short time (less than 2 seconds, with a result or with an exception). But for some elliptic curves the call E.rank() takes more than 1 hour ...

So, my idea is: I would like to call E.rank(only_use_mwrank=True) in a separate thread - and to terminate the call / the thread after - let's say - 5 seconds.

I tried to find solutions in the internet - but it seems it is very complex because (a) it is not easy to do it in python, (b) it is even more complex to do it with a library call that is in cpython (like E.rank seems to be).

Is there any way how I could do this in sage / python / cypthon?

Thanks a lot Daniel Lauer

Example:

# In this example, myProc2 does not return for 1 hour ... and therefore "blocks" myProc3. 
# You may run the example in SageMathCell (http://sagecell.sagemath.org).
def myProc1():
  print("starting myProc1")
  E = EllipticCurve([0, 146, 0,  1556, 0])
  r = E.rank(only_use_mwrank=True)
  print("rank = {}".format(r))
  print("finished myProc1")

def myProc2():
  print("starting myProc2")
  E = EllipticCurve([0, - 249730248677555343372, 0,  158929357618867398869672381174059102500, 0])
  E.rank(only_use_mwrank=True)
  r = E.rank(only_use_mwrank=True)
  print("rank = {}".format(r))
  print("finished myProc2")

def myProc3():
  print("starting myProc3")
  E = EllipticCurve([0, 643, 0,  -264, 0])
  E.rank(only_use_mwrank=True)
  r = E.rank(only_use_mwrank=True)
  print("rank = {}".format(r))
  print("finished myProc3")

myProc1()
myProc2()
myProc3()
edit retag flag offensive close merge delete

Comments

1

See

alarm?
FrédéricC gravatar imageFrédéricC ( 2022-04-02 18:57:24 +0200 )edit

2 Answers

Sort by » oldest newest most voted
0

answered 2022-05-22 02:47:02 +0200

William Stein2 gravatar image

updated 2022-05-22 02:47:31 +0200

Hi, A long time ago I wrote a decorator called @fork that basically automates what is going on under the hood in the multiprocessing answer by dan_fulea. See https://doc.sagemath.org/html/en/refe... In particular, note that @fork has a timeout option. Hopefully this is helpful...

edit flag offensive delete link more
0

answered 2022-05-20 00:51:02 +0200

dan_fulea gravatar image

Here is a piece of code computing ranks for all congruent number elliptic curves $y^2 = x^3 - k^2x$ with $k$ from $150$ to $180$, well, at most three seconds per curve.

import signal

def get_rank(E):
    try:
        return E.rank()
    except Exception:
        print(f'*** ERROR FOR {E}')

# Introduce a handler at timeout to be passed as argument to the signal.signal
def handler(signum, frame):
    raise Exception("TIMEOUT")

dic = {}
for k in [150..180]:
    E = EllipticCurve(QQ, [-k^2, 0])
    # Register the handler inside signal.signal and set timeout
    signal.signal(signal.SIGALRM, handler)
    signal.alarm(3)             # just three seconds for the rank computation, no more

    try:
        dic[k] = get_rank(E)    # computation here as an explicit call in a separate line
    except Exception:
        dic[k] = None

    print(f'k = {k} :: rank = {rk}')
    signal.alarm(0)             # close the alarm

Results:

sage: dic
{150: 1,
 151: 1,
 152: 1,
 153: 0,
 154: 2,
 155: None,
 156: 1,
 157: None,
 158: 1,
 159: 1,
 160: 0,
 161: 2,
 162: 0,
 163: 0,
 164: 2,
 165: 1,
 166: 1,
 167: 1,
 168: 0,
 169: 0,
 170: 0,
 171: 0,
 172: 0,
 173: None,
 174: 1,
 175: 1,
 176: 0,
 177: 0,
 178: 0,
 179: 0,
 180: 1}
sage:

And the more difficult expected curve with $k=157$, together with two other curves, were not finished in time. So in principle, this should work in the similar case in question...

In your case, something like the following may be of interest:

for data in [ [0, 146, 0,  1556, 0]
              , [0, -249730248677555343372, 0,  158929357618867398869672381174059102500, 0]
              , [0, 643, 0, -264, 0]]:

    signal.signal(signal.SIGALRM, handler)
    signal.alarm(60)             # sixty seconds for the rank computation, no more

    E = EllipticCurve(QQ, data)
    try:
        dic[k] = get_rank(E)    # computation here as an explicit call in a separate line
    except Exception:
        dic[k] = None

    print(f'{E}\nrank = {rk}\n')
    signal.alarm(0)             # close the alarm

But unfortunately, (i suppose) the second curve was not inside python to catch the signal, who knows, some factorization problems or worse may have been delegated to pari/gp, and even a manual Control+C in the interpreter did not interrupt the loop. I had to manually kill the sage process from an other terminal. (This is a lucky case, sometimes there is no other terminal that can be opened...)

So an other solution was needed. I tried...

import multiprocessing
import traceback

def get_rank(E, dic):
    try:
        dic[E.a_invariants()] = E.rank(only_use_mwrank=True)
    except Exception:
        traceback.print_exc()
        print(f'*** ERROR FOR {E}')

manager   = multiprocessing.Manager()
ranks_dic = manager.dict()    # used to record the results of the rank computations

for data in [ [0, 146, 0,  1556, 0]
              , [0, -249730248677555343372, 0,  158929357618867398869672381174059102500, 0]
              , [0, 643, 0, -264, 0]]:

    E = EllipticCurve(QQ, data)
    print(f'... starting rank computation for:\n{E}') 
    P = multiprocessing.Process(target=get_rank, args=(E, ranks_dic))

    P.start()     # start the computation
    P.join(30)    # Wait for 30 seconds or until process finishes

    if P.is_alive():
        print(f"Terminating the rank computation for:\n{data}\n")
        P.terminate()    # or to be "sure" it is gone...
        # P.kill()

print('Computed ranks:')
for a_invarinats, rk in ranks_dic.items():
    print(f'rank = {rk} for {a_invarinats}')

Results:

... starting rank computation for:
Elliptic Curve defined by y^2 = x^3 + 146*x^2 + 1556*x over Rational Field
... starting rank computation for:
Elliptic Curve defined by y^2 = x^3 - 249730248677555343372*x^2 + 158929357618867398869672381174059102500*x over Rational Field
Terminating the rank computation for:
[0, -249730248677555343372, 0, 158929357618867398869672381174059102500, 0]

... starting rank computation for:
Elliptic Curve defined by y^2 = x^3 + 643*x^2 - 264*x over Rational Field
Computed ranks:
rank = 0 for (0, 146, 0, 1556, 0)
rank = 0 for (0, 643, 0, -264, 0)

Note that the computations were started one by one, not exactly the intension of the imported package.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2022-04-02 17:17:01 +0200

Seen: 34 times

Last updated: May 22