-
-
Notifications
You must be signed in to change notification settings - Fork 435
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Hecke series for overconvergent modular forms #12043
Comments
comment:2
Reviewed this patch, everything works perfectly and looks nice. |
comment:3
Ignore the previous comment, I have not reviewed this. Sorry! |
comment:5
(For the record: I am in the process of reviewing this.) |
comment:6
Hi Alan, This is really nice code: I'm very happy that you chose to make this Sage implementation available. I am preparing a second reviewer patch, to be applied on top of your patch, which mainly cleans up the documentation and removes some functions which already existed in Sage under different names (such as a lot of the routine linear algebra stuff). However, I've not completed my review, because I think there's a serious lurking bug. The problem is this. The code in There are a few other (relatively minor) things that puzzle me about this implementation, as well, and I'd be grateful if you could explain them to me.
|
comment:7
Here's my reviewer patch. Comments and questions in the code are marked with XXX. I emphasize that it's incomplete, because I stopped once I realized the problem with Z versus Q generators. Still it does a large part of the work of hooking your code into Sage (adding the new module to the global namespace, to the reference manual, etc) and thus I'd be grateful if you worked on top of this patch for the next round of corrections. |
comment:8
Dear David Many thanks for your message, and for looking so carefully at the code. This is greatly appreciated! I am a novice at the SAGE review process, so will wait to get advice from Sebastian (Pancratz) on exactly what to do next with On the Z versus Q basis, I was aware of that problem. In fact, when modformsring=false the algorithm will not terminate When modformsring=true, as you noticed the algorithm defaults to modformsring = false when the ModularFormsRings.generators() gives non p-adically integral generators. I did ask William (Stein) about That said though I think your point is a very good one. In particular, if one had an integral_generators() function then On your other points:
Best wishes Alan. Replying to @loefflerd:
|
comment:9
Replying to @sagetrac-lauder:
Are you asking for integral_generators to return (a) modular forms which have integral q-expansions and are Q-algebra generators for the ring of all modular forms, or (b) Z-algebra generators for the ring of integral modular forms? The former would be completely trivial to do. The latter is certainly possible, but would be harder; in fact it would be a great thing to have anyway, but it would be much slower than the current implementation of course.
I'm pretty sure it's true that for all N, the ring of modular forms of level N is generated over Q by forms of weight at most 6. Working out the details is a fiddly exercise which I should probably just sit down and do one of these days. But of course to get integral generators you might need larger weights. Perhaps using some more algebraic geometry one can bound above the max weight needed for generators over Zp (at least for p not dividing the level). There is some yoga with ample line bundles that I've never quite got my head around.
I'm not sure what the policy is on including algorithms which aren't known to terminate, I'd have to check. That would simplify the code a lot, which would be nice. We can certainly make the generators code return generators over Q which were integral (but not necessarily integral generators), which would mean we could remove the fallback code.
OK, thanks; I missed that in the paper.
Well, thanks here are due to Jan, not me :-)
There is a choice to be made here: one can either work consistently with power series objects, or consistently with vectors. You seem to be suggesting the first, but I'd strongly recommend the second: this allows you to use Sage's very fast echelon form routines, which are written in C, rather than using hand-rolled Python versions which would inevitably be much slower. There is some code in modforms/find_generators.py which does something quite similar to this, and that works with vectors where possible.
It's really simple: all I did was to type
and that does the job.
I see. Yes, that makes a lot of sense -- if your random products of the basis in random_new_basis_modp are landing in a specific subspace with high probability then it's clearly not good. You'll notice that in the reviewer patch I got rid of a call to |
comment:10
Dear David Thanks for your message. On integral_generators, ideally I would like (b). Regarding the algorithm terminating, I thought very briefly about bounding the number of random q-series I followed your suggestion, and cut row_reduced_form altogether, replacing the list of q-series modulo p with a matrix. This Best wishes Alan. Replying to @loefflerd: |
comment:11
Dear David I have applied your patch (with Sebastian's help) and then made my changes. I created a new patch myself: hopefully I did the right thing. In any case, I will email you my new source code directly (just in case I messed up). Note that your new version failed on a few tests on my machine: there was a stray "print" statement you must have put in sometime; also, it complained about some alteration you made to the little function for testing if a weight list was valid. I did not understand what was happening with the latter, so I have not touched this: when I tested my new version it passed everything OK except that weight list one. I tried to address all of your smaller concerns. The only substantial change was that I altered the random_new_basis_modp function so that it does not waste time changing between matrices and lists: this also involved a small change to the complementary_spaces_modp function. I meant to check why the new version was slower for large p, but forgot. Perhaps you could have a look at whether using eisenstein series over Q is slowing down the computation of E_(p-1) for, say, p = 79, N = 1, k = 2 and m = 3. Anyway, many thanks again for all the improvements you made to the code! Best wishes Alan. |
Reviewer: David Loeffler |
Changed author from lauder to Alan Lauder |
comment:12
Replying to @sagetrac-lauder:
No problems there, the patch applied fine.
I see what's happened there -- silly mistake on my part, I'll fix it.
The new version is actually about 50 times faster. For instance, computing 10000 terms of E_{78} mod 79 takes 10.23 seconds with your old code, and 0.49 seconds with the new code.
No problem. I am a bit busy at the moment, but when I get a chance I will look at your changes, sort out the last few minor issues and then I think it'll be good to go. Best regards, David |
comment:13
Dear David Many thanks for your message. I'm glad it worked! On the level 1 code, on my machine setting p = 79, N = 1, k = 2, m = 3, the original version took 40s and the new version 43.5s. The algorithm is not randomised here, so something genuinely appears to be taking longer. Anyway, perhaps when you come to try out the new code you could have a quick look at this. Best wishes Alan. |
comment:14
Whatever is causing the slowdown, it's not my changes to the Eisenstein series code. With the parameters you suggest, your original code takes 0.987 seconds per call to "eisen_series", my first round of changes in attachment: trac_12043-reviewer.DRAFT.patch gets this down to 0.080, and with some minor tinkering elsewhere in the Sage library I can speed this up another whole order of magnitude, to 0.009 seconds. However, there is indeed a small and persistent slowdown, which cancels out the speedup in |
comment:15
OK, so I got to the bottom of this. Something like 90% of the running time for Ep1p = Ep1(q**p)
Ep1pinv = Ep1p**(-1)
G = Ep1*Ep1pinv These are slowed down slightly by my changes, since my first reviewer patch added an
With the code above changed to Ep1p = (Ep1.add_bigoh(ceil(Ep1.prec() / ZZ(p)))).V(p)
Ep1pinv = Ep1p**(-1)
G = Ep1*Ep1pinv the execution time drops from 43.24 s to 2.68 s. It's a bit of a mystery to me why the first version is quite so slow; I guess it's calling some general-purpose routine for composition of power series, not realizing that what we're substituting is so simple. How does the new timing compare with Magma? |
comment:16
Dear David Many thanks for looking into this! By the way: I am in Japan for the next five weeks, with very slow internet access and a keyboard that keeps switching to Japanese (then I have to start all over again). So it has taken about an hour to get this far ... That timing is about the same as magma now. It is great you spotted that! I did try a larger example: p = 59, N = 1, k = 2 and m = 5. Here magma was about 7 seconds and sage 28. So I think there is probably still a big difference, even in level 1. (Magma code is on my website, in case you have access to magma and want to try it.) Incidentally: you are of course quite right that the end of the Miller basis gives the complementary spaces, but the start has nothing particularly to do with the image ... Please correct the blurb appropriately. (See my silly comment in the patch.) I am going to finish now, before the keyboard goes funny and I have to start again. Best wishes Alan. |
comment:17
Here's what I get with all my optimizations:
So the Sage implementation has pulled ahead of the Magma one now, at least for these level 1 cases. I think there is only one more thing we need to do, if we're willing to live with the unproven conjecture about weights of generators. That is, to modify the ModularFormsRing code so the generators it returns are always integral, and so that the ZZ-submodule they generate is saturated in weights up to the given bound. This is not too hard to do -- I already have code that does it, I just need to merge it into the Sage library. Then I think we can get this in (modulo yourself or someone else reviewing my contributions). I'm not saying that there isn't room for further optimizations, but those can come in subsequent tickets. |
All patches folded into one |
comment:18
Attachment: trac_12043-all.patch.gz I've uploaded a new revised version, in two forms: attachment: trac_12043-part4.patch is the difference from the previous version, and attachment: trac_12043-all.patch is a single patch combining the effects of the four patches so far. This version is dependent on two new tickets #12724 and #12740. The first of these (already positively reviewed, thanks Alex!) adds options for different normalizations to the top-level Eisenstein series function, incorporating the functionality from the I think this is ready to go now. All that's required is for someone to have a look at my part4 patch and verify that the changes look reasonable. |
comment:19
Apply trac_12043-all.patch (for the patchbot) |
minor fix -- apply over previous folded patch |
comment:20
Attachment: 12043-fix.patch.gz Apply trac_12043-all.patch, 12043-fix.patch (for patchbot). This patch just changes the output type when a list of spaces is called for, all of which are zero (returning a list of ones). |
comment:21
Thanks for fixing this David, everything works absolutely impeccably. |
Merged: sage-5.3.beta0 |
Additional patch |
This comment has been minimized.
This comment has been minimized.
comment:23
Attachment: 12043_long_time.patch.gz Additional patch attachment: 12043_long_time.patch needs review. This is a blocker patch. |
Changed reviewer from David Loeffler to David Loeffler, Jan Vonk |
comment:25
Looks harmless enough to me. I'd be happy to reinstate the positive review, but I don't have sufficient trac privileges to reopen the ticket in order to do so. |
comment:26
No need to reopen the ticket, I'll just merge the additional patch. |
Computes to any required p-adic precision the characteristic series of the
Atkin U_p operator on the space of p-adic overconvergent modular forms of
given weight k and level N.
Apply:
Depends on #12724
Depends on #12740
CC: @loefflerd
Component: modular forms
Author: Alan Lauder
Reviewer: David Loeffler, Jan Vonk
Merged: sage-5.3.beta0
Issue created by migration from https://trac.sagemath.org/ticket/12043
The text was updated successfully, but these errors were encountered: