On Tue, Aug 17, 2010 at 3:31 PM, William Stein <wst...@gmail.com> wrote:
> 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.
I was just thinking about that this morning :). I plan to attack it
later this week.
- Robert
--
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
