On 17 August 2010 23:31, 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...
>
That's quite true. The set of curves on which my algorithm will
deliver in reasonable time is a strict subset of those for which we
know the answer already and have it in the database. (The numbers in
the database were computed either by both my algorithm and Mark's, and
compared, or -- for the larger conductors -- just by his). That
makes it quite redundant to revive my implementation (which would be
nontrivial since I commented out that code in eclib years ago and have
made many other changes to the rest of the code since).
> 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):
>
I guess this is what I think of as the Merel linear algebra method.
This was also once in eclib.....(but only for elliptic curves, yours
is more genera as you say).
> 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
>
Excellent. Delaunay replied to me saying that he was away from home
but when he returns he will try to locate his own implementation,
which is in a GP script. That might well help the implementer. Also,
in one of his replies on this discussion (not copied to the list so I
hope he will not mind me quoting hime here, Mark says
"My understanding was that Christophe had more details about the analytic
questions (like inverse Mellin transforms and round-off error -- neither
referee insisted that I say anything there), while I spent more time with
the bad Euler factors (having tracked down the Coates-Schmidt paper where
they essentially appear, though with a few accounting errors, and with a
method of computation not explicitly given). I also took an "experimental"
view of the question, computing the modular degree for a large dataset of
curves, whilst his focus was more "French" (if I may), in that it gives a
theoretical description and then (almost grudgingly) appends a few examples."
This difference of emphasis is significant. Mark wanted to collect a
lot of data, so wanted his program to be fast, while Christophe just
wanted some examples to show that the method was feasible. Hie script
may still be useful though.
John
> 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
>
--
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
