On Tue, Aug 17, 2010 at 3:11 PM, Dr. David Kirkby
<david.kir...@onetel.net> wrote:
> On 08/17/10 09:26 AM, John Cremona wrote:
>>
>> At last, a contributiuon to this thread which actually addresses my
>> original question!
>>
>>>> In contrast, it seems sympow is not used by many people. The fact there
>>>> are
>>>> no bug reports of it not working on the public servers shows how little
>>>> it
>>>> is used. (If someone actually tried to run many of the examples, they
>>>> will
>>>> find they don't work).
>>>
>>> There is 1 "example" -- the modular degree function --  that is 1000
>>> times more important than the rest.    Here's me *using* sympow:
>>>
>>> sage: E = EllipticCurve('5077a'); E
>>> Elliptic Curve defined by y^2 + y = x^3 - 7*x + 6 over Rational Field
>>> sage: E.modular_degree()
>>> 1984
>>>
>>
>> This is what I thought.  I could provide modular degree from eclib but
>> it would be *vastly* slower.  I myself stopped using my own modular
>> degree function (despite publishing a paper describing the algorithm,
>> which I was rather proud of at the time) and started to use sympow
>> (which was then called ec) for the elliptic curve database, since my
>> own version took much too long.  In fact it is fair to say that for
>> any elliptic curve not in the database (whose modular degrees are
>> known and in the database), my implementation would not finish in
>> reasonable time, which makes my "offer" worth little.
>
> John,
>
> I think if you are able to compute this with your package, it would be
> useful addition to Sage. Having two independent algorithms, implemented by
> two different people, could be useful, despite one being much slower than
> the other.

The difference in complexity is very significant.  John's is probably
O(N^3), whereas Mark's is O(sqrt(N)).  This is a *dramatic* difference
in practice.  It means hundreds of years versus a few seconds...

Also, something that is close to John's algorithm is already in Sage,
which I implemented.  Well, this is technically a third distinct
algorithm (which is much more general in some ways):

sage: A = J0(54).new_subvariety()[1]
sage: A.modular_degree()
2
sage: EllipticCurve('54b').modular_degree()
2

> I think it's particularly so in this case, given the concerns some people
> have about the code quality.
>
>> It would be a student project to reimplement Mark W's algorithm (Here:
>> http://www.emis.ams.org/journals/EM/expmath/volumes/11/11.4/pp487_502.pdf)

This is what should happen.  After somebody implements his algorithm
in Sage, then
we can (re)move Sympow.  Here's a trac ticket:

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

I wish Robert Bradshaw would finish
http://trac.sagemath.org/sage_trac/ticket/9193, by the way.



William

-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Reply via email to