Should we include Michael Stoll's ratpoints as a standard spkg?

[Robert Miller]

ratpoints is a program for finding points of bounded height on curves
of the form

y^2 = a_n x^n + ... + a_1 x + a_0.

A version of ratpoints was the starting point of John Cremona's
mwrank, but since then there have been substantial improvements. I
have been working on a Sage-native implementation of 2-descent on
elliptic curves, using ratpoints, GMP, and FLINT. It is significantly
faster than Magma, which is significantly faster than mwrank (at least
on the curves I've been looking at-- I haven't done extensive
benchmarking yet).

The webpage for the software is here:

http://www.mathe2.uni-bayreuth.de/stoll/programs/index.html

The trac ticket is here:

http://trac.sagemath.org/sage_trac/ticket/5854

There are some memory leaks in ratpoints, but we will work on fixing
these next week at Dagstuhl.

Statistics:
spkg size: 255K
time to build: 5.6 secs

What does everyone think?

[John Cremona]

2009/5/21 Robert Miller <rlmil...@gmail.com>:

I will certainly be checking this out! Two points before I do:

1. For years after Magma re-implemented mwrank (I gave them my code,
no license, but they wrote tehor own impelmentation) John Cannon was
frustrated that it remained slower than mwrank itself. I had not
noticed that that had changed. On the other hand tehre are things in
mwrank (e.g. second descents) which are not -- I think -- in Magma,
and testing curves in the database is a bit too easy.

2. It is not true to say that "A version of ratpoints was the starting
point of ... mwrank", not at all. mwrank does 2-descent, during the
course of which it has to search for points on such curves. For the
first 10 years of mwrank that was done by my own code. Then Stoll's
ratpoints came along which did that part faster (but did no kind of
descent at all, it was just a fast point search); so I adapted it and
put it into mwrank in 1999. My older searching code is still in
there, in fact if you change line 61 of src/qrank/mrank1.cc from this:
#define QSIEVE_OPT 0 // uses Stoll's sieve
so something else it wil still work (or it did last time I tried it,
so not guaranteed).

I'm looking forward to working on this. Note that what Robert has
done goes way way beyond the current title of #5854 ("Include Michael
Stoll's ratpoints in Sage"); it also implements a complete native
Sage version of (a lot of) mwrank, and he has done it remarkably fast.
Well done!

John

> >
>

[Robert Miller]

John,

On May 21, 9:38 am, John Cremona <john.crem...@gmail.com> wrote:
> 2009/5/21 Robert Miller <rlmills...@gmail.com>:

> 2. It is not true to say that "A version of ratpoints was the starting
> point of ... mwrank", not at all.   mwrank does 2-descent, during the
> course of which it has to search for points on such curves.  For the
> first 10 years of mwrank that was done by my own code.  Then Stoll's
> ratpoints came along which did that part faster (but did no kind of
> descent at all, it was just a fast point search);  so I adapted it and
> put it into mwrank in 1999.  My older searching code is still in
> there, in fact if you change line 61 of src/qrank/mrank1.cc from this:
> #define QSIEVE_OPT 0 // uses Stoll's sieve
> so something else it wil still work (or it did last time I tried it,
> so not guaranteed).

Sorry -- I was only referring to the fact that mwrank currently uses
an out-of-date version of ratpoints.

Anyway, I'll cast my vote:

+1 for including ratpoints (once leaks are fixed) in Sage standard.

[William Stein]

+1 since we already include an old version of ratpoints. I think
voting for this
is a total no brainer.

William

[David Roe]

+1 from me as well.

[John Cremona]

2009/5/21 Robert Miller <rlmil...@gmail.com>:

+1 (of course). And no need to apologise!

John

> >
>

[Alex Ghitza]

+1, and thanks for your work on this!

Alex

--
Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne
-- Australia -- http://www.ms.unimelb.edu.au/~aghitza/