#11875: Correct general brokenness of Farey symbols
-----------------------------+----------------------------------------------
Reporter: davidloeffler | Owner: craigcitro
Type: defect | Status: new
Priority: major | Milestone: sage-4.7.3
Component: modular forms | Keywords: modular subgroup
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Changes (by GeorgSWeber):
* cc: hmonien (added)
Comment:
Hi all,
the structural data of an arithmetic subgroup, that one needs to compute
for the modular symbols "integrality algorithm", is more or less the same
than what one needs for Farey symbols (for some discussion of the former,
see http://groups.google.com/group/sage-
nt/browse_thread/thread/a653b4498fa5cb67#).
FWIW, I have put some "needs work" code for that (pure Python, building
upon the existing ArithmeticSubgroup framework in Sage) at trac #10857.
It needs quite some polishing (especially a renaming and a complete
reordering of the functions), but works for all arithmetic subgroups,
features examples of non-congruence subgroups (taken elsewhere from Sage),
and for certain classes of groups (Gamma, Gamma_1, Gamma_0) there are
special algorithms that compute this structural data in linear time
(w.r.t. to the subgroup index in SL2Z), not quadratic time (which is the
generic case).
Explicitly, on my 2 GHz machine, the code there computed generators and
coset representatives for Gamma(64) in about 17 seconds and for Gamma(128)
in about 478 seconds.
Since then, I didn't find the time to continue the work on that code (if I
had free time to spare for Sage, I'd rather review #5048, sigh), or else I
would have finished e.g. the dummy "def z_farey_symbol_data(self):" there
...
My proposal for continuing with #11709 and this #11875 here, would be to
separate off the "plotting" parts of #11709 (which I dearly would like to
have ready in Sage), which seem to be uncontroversial, and get them into
Sage.
Having done that, and Hartmut and Martin still being "on fire", the next
step might be to do the reality check, whether using C++ for computing the
Farey symbol structural data really gives the speed advantage, worth all
the trouble not coding these algorithms directly in Python (or Cython).
Please don't get me wrong, you have my greatest respect for executing the
addition of a new cpp file to the Sage library! There are probably lots of
places in the Sage development documentation that could benefit from this
experience, think not only of the last necessary patches from Leif, but
also all this "module_list.py" stuff, let alone the .rst documentation
(kudos to you for including pictures!!), and what not ...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11875#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
