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