Opened 7 years ago
Closed 6 years ago
#16976 closed enhancement (fixed)
Conjugacy classes and rational period functions for Hecke triangle groups
Reported by:  jj  Owned by:  

Priority:  major  Milestone:  sage6.6 
Component:  modular forms  Keywords:  hecke triangle group conjugacy class rational period function 
Cc:  vdelecroix  Merged in:  
Authors:  Jonas Jermann  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  7dcee34 (Commits, GitHub, GitLab)  Commit:  7dcee3441862c9af9f1a63e1c3c8d4b957d2d705 
Dependencies:  #16936  Stopgaps: 
Description (last modified by )
The ticket adds several new features to Hecke triangle groups (resp. elements):
 "Block" decomposition of elements. This determines the conjugacy type of elements
 Several alternative representation methods for elements
 Lambdacontinued fraction expansion of fixed points (exact!) In particular the primitive part of a group element can be determined
 Checks and generation of reduced and simple elements, Checks for Hecke symmetry
 Slash operator
 Rational period functions associated to hyperbolic elements (resp. their fixed point)
 class number and class representatives for a given discriminant In particular discriminants can be listed, so can all simple/reduced elements for a given discriminant
 Linking numbers
 improved documentation and minor additions/modifications
Some remarks:
 The code to determine class numbers/representatives is very slow at the moment. :(
 The case n=infinity is excluded / not supported yet :(
Change History (39)
comment:1 Changed 7 years ago by
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
 Commit changed from ff8c466bf9dcaec73cba70fa710c5bdebc95c23c to e87adec65706c74c49c574b82de8a4e4d340a710
comment:3 Changed 7 years ago by
 Commit changed from e87adec65706c74c49c574b82de8a4e4d340a710 to 8169e6d16a60ab533332d6a22cfe0b7f8571f760
Branch pushed to git repo; I updated commit sha1. New commits:
8169e6d  support enlisting a (maybe generating?) set of rational period functions for a given weight and discrimiant

comment:4 Changed 7 years ago by
 Commit changed from 8169e6d16a60ab533332d6a22cfe0b7f8571f760 to 24cd0734322a35cae5a6f7fd8b460aa8d55fe0f0
Branch pushed to git repo; I updated commit sha1. New commits:
24cd073  documentation bugfixes

comment:5 Changed 7 years ago by
 Status changed from needs_review to needs_work
 Work issues set to want: positive block exponents
comment:6 Changed 7 years ago by
 Commit changed from 24cd0734322a35cae5a6f7fd8b460aa8d55fe0f0 to cff4898f6c4e654556de84e9a876680e89f173cd
comment:7 Changed 7 years ago by
 Commit changed from cff4898f6c4e654556de84e9a876680e89f173cd to d14ee40b27fc54f5dc2e0ffe1bbb5a5f1c57e5cc
Branch pushed to git repo; I updated commit sha1. New commits:
d14ee40  support for the calculation of linking numbers

comment:8 Changed 7 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
comment:9 Changed 7 years ago by
 Work issues want: positive block exponents deleted
comment:10 Changed 7 years ago by
 Commit changed from d14ee40b27fc54f5dc2e0ffe1bbb5a5f1c57e5cc to c5df163f8c77466df4c7ea2d7efa360e8f17761c
Branch pushed to git repo; I updated commit sha1. New commits:
c5df163  drastically simplified how conjugacy types are represented: now simply the maximal representative from the class is used (using lexicographical ordering), some documentation improvements

comment:11 Changed 7 years ago by
 Commit changed from c5df163f8c77466df4c7ea2d7efa360e8f17761c to aad579b20b12a1735996dedce1d3a9fa2c7f04bf
Branch pushed to git repo; I updated commit sha1. New commits:
aad579b  check elements by default

comment:12 Changed 7 years ago by
 Commit changed from aad579b20b12a1735996dedce1d3a9fa2c7f04bf to 6701b8dacc71116d55afa06d9c70ce09c3c86fd6
Branch pushed to git repo; I updated commit sha1. New commits:
87df16c  Annotations to Jonas's implementation.

05e551d  address review remarks

5c0f38e  Merge branch 'u/jj/theta_group' into u/jj/hecke_lseries

b6adc39  Merge branch 'u/jj/hecke_lseries' into u/jj/triangle_groups

6701b8d  Merge branch 'u/jj/triangle_groups' into u/jj/triangle_conjugacy

comment:13 Changed 7 years ago by
 Commit changed from 6701b8dacc71116d55afa06d9c70ce09c3c86fd6 to f8b5198698a377f8829c888e5e68071304219d30
Branch pushed to git repo; I updated commit sha1. New commits:
f8b5198  bugfix: always try to simplify algebraic expressions before calculations (pari_field bug for AA?), as a consequence many operations (in particular continued fractions) are much faster, improved version of root_extension_embedding

comment:14 Changed 7 years ago by
 Commit changed from f8b5198698a377f8829c888e5e68071304219d30 to df7816dce02f42f2f6fa38b7797f84359578d8c2
comment:15 Changed 7 years ago by
 Cc vdelecroix added
 Description modified (diff)
comment:16 Changed 7 years ago by
 Commit changed from df7816dce02f42f2f6fa38b7797f84359578d8c2 to 94dae505a9b10515afb7c0013412e4d92a01626d
comment:17 Changed 7 years ago by
 Status changed from needs_review to needs_work
Hello Jonas,
It is always a bad choice to make a lot of modifications in one patch (especially because no reviewer will like it). From the description of your ticket, it looks like you would better have 2 or 3.
Some remarks:
 Why did you choose to put the code for triangle groups in
sage.modular.modform_hecketriangle
. As you can see elements of arithmetic groups are insage.modular.arithgroup
while the code relative to modular forms is insage.modular.modform
. People interested in Hecke groups are not necessarily interested in modular forms.  As you might have seen, the
ArithmeticSubgroupElement
class inherits directly fromMultiplicativeGroupElement
and not fromMatrixGroupElement_generic
. The reason is performance as most methods of2x2
matrices (such as det, traces, ...) are much faster using explicit formulas. Moreover, the class for arithmetic group element only have four slots for the elements a,b,c,d which is much simpler than a list of vectors for storing rows.  Is
string_rep
standard ? I thought thatstr
would have been better.  You must put useful tests in the class
HeckeTriangleGroupElement
and move it from the__init__
method to the main documentation of the class. These examples are here to help the users. In particular, start with code that works, not with potential failure.  There are too much
cached_method
. In an ideal world there should be none. A python objects takes some amount of RAM, and each cached method stores python objects. Abusing with thecached_method
implies that you can not deal with huge list of Hecke triangle group element. You should basically remove all of them unless you have a very strong argument for having it (e.g.root_extension_embedding
inHeckeTriangleGroup
).  Why do you use the algebraic field
AA
instead of number fields ? It is much slower in all situations. Note that there is a (relatively slow) method for checking that a number is positive:.is_real_positive
.  What is the point of the method
m.root_extension_embedding()
? You may use directlym.parent().XXX
.
Vincent
comment:18 Changed 7 years ago by
 Commit changed from 94dae505a9b10515afb7c0013412e4d92a01626d to 8f31651050e64d4b117f2cbd4671a72df111ff7c
Branch pushed to git repo; I updated commit sha1. New commits:
8f31651  removed some cached_methods

comment:19 Changed 7 years ago by
 Commit changed from 8f31651050e64d4b117f2cbd4671a72df111ff7c to 3c7ca0f2bf33d3fdec7b79c353b28ccc01cd419d
Branch pushed to git repo; I updated commit sha1. New commits:
3c7ca0f  add documentation and doctests to coerce_AA

comment:20 Changed 7 years ago by
Hi Vincent
Thanks a lot for the feedback/review!
It is always a bad choice to make a lot of modifications in one patch (especially because no reviewer will like it). From the description of your ticket, it looks like you would better have 2 or 3.
Yeah, I realize that. I'm very sorry! Most of the changes are related/interacting.
 Why did you choose to put the code for triangle groups in
sage.modular.modform_hecketriangle
. As you can see elements of arithmetic groups are insage.modular.arithgroup
while the code relative to modular forms is insage.modular.modform
. People interested in Hecke groups are not necessarily interested in modular forms.
Mainly because it was originally a stub implementation. But yes that could be changed. What about doing it in a separate ticket?
 As you might have seen, the
ArithmeticSubgroupElement
class inherits directly fromMultiplicativeGroupElement
and not fromMatrixGroupElement_generic
. The reason is performance as most methods of2x2
matrices (such as det, traces, ...) are much faster using explicit formulas. Moreover, the class for arithmetic group element only have four slots for the elements a,b,c,d which is much simpler than a list of vectors for storing rows.
Matrix group operations are used at several places. I choose MatrixGroupElement_generic because I considered it simpler / less error prone than reimplementing all operations. If it makes a big difference for performance I can try to change it. What about doing it in a separate ticket?
 Is
string_rep
standard ? I thought thatstr
would have been better.
I used 'string_rep' as a helper function for _repr_ (since I have several possible representations) but 'str' would be fine by me as well (if it isn't used for other purposes).
 You must put useful tests in the class
HeckeTriangleGroupElement
and move it from the__init__
method to the main documentation of the class. These examples are here to help the users. In particular, start with code that works, not with potential failure.
The way I documented my code I put the main documentation of classes resp. their usage in the readme.py file.
 There are too much
cached_method
. In an ideal world there should be none. A python objects takes some amount of RAM, and each cached method stores python objects. Abusing with thecached_method
implies that you can not deal with huge list of Hecke triangle group element. You should basically remove all of them unless you have a very strong argument for having it (e.g.root_extension_embedding
inHeckeTriangleGroup
).
I tried to remove as many cached_methods as possible without causing a major performance drop. Some of them would cause an overall 30% drop in performance (according to doctests at least) if removed. One reason for this is also that group elements are not uniquely represented, so if the basic elements aren't cached several expensive calculations on them would be unnecessarily repeated (in particular simply displaying the element would probably take much longer).
One idea might be to use UniqueRepresentation? for elements as well but in this instance I am not really sure how (resp. what to put in classcall). Again this is a change which is not related to the ticket so it could be done in a separate ticket.
 Why do you use the algebraic field
AA
instead of number fields ? It is much slower in all situations. Note that there is a (relatively slow) method for checking that a number is positive:.is_real_positive
.
.is_real_positive seems to simply use .n() to numerically decide positivity. In particular it requires some embedding into e.g. RR or RIF. I choose AA as the default embedding because it is the most versatile base for further embeddings. If I "RR" or "RIF" would be used then embeddings into AA wouldn't be easily possibly anymore.
I.e. I choose generality/flexibility/versatility over performance. If performance becomes a big issue my suggestion would be to explicitely specify an embedding for those cases. E.g. For fixed points (which live in a relative number field extension) I needed this (in particular because there is no default embedding) and there is the root_extension_embedding method for that purpose.
 What is the point of the method
m.root_extension_embedding()
? You may use directlym.parent().XXX
.
For elements we know the discriminant which is given as an argument to the parent function.
Jonas
comment:21 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:22 Changed 7 years ago by
 Cc mraum removed
comment:23 Changed 6 years ago by
 Milestone changed from sage6.4 to sage6.5
comment:24 Changed 6 years ago by
 Status changed from needs_review to needs_info
Hi,
It is standard in Sage to have documentation directly attached to the objects. If there is a need for a larger document that would serve as explanation or tutorial, then it is fine. But it is not where the main documentation should be. Moreover, such document should be listed in the "Thematic tutorials".
I am still not happy with the cached_method
. If it is long to compute the decomposition into generators from the matrix, then do not make it appear in _repr_
. It is a nonsense to argue that some methods must be cached because of __repr__
. Either this decomposition is important for computations, in which case it must be computed at the creation (and in parallel with the matrix multiplication). Or it is not, in which case it does not matter that it is long to compute. This concerns _basic_data
and _primitive_bloc_data
. On the other hand, why continued_fraction
is still cached?
If the information contained in _basic_data
, _primitive_bloc_data
and _continued_fraction
are approximately equivalent, you can choose one of them for being cached. From what I understand:
_primitive_block_data
: built fromcontinued_fraction
_block_data
: generalization of_primitive_block_data
so there is for sure no need to cache all of them. And using UniqueRepresentation
for elements is a bad idea (it will cost too much).
line 2700
.. TODO: Improve the documentation!
Who will do that?
I do have plenty of other remarks that I can partly implement myself. But I want the one above to be settled before going further.
Vincent
comment:25 Changed 6 years ago by
Hi Vincent,
Thanks a lot for the response. I am sorry that you are so unhappy with the code. :(
Regarding the documentation: This could be done in a separate ticket (it relates to much more than just this ticket which is already rather large). I followed the advice of Martin Raum when I started, sorry if the documentation is in the wrong spot.
Regarding the cached methods: Of course this is not about repr (it only comes into play if the representation method is changed). The result of the cached calculation is rather short compared to the possibly really long computations to get it (for all examples above). More importantly the cached results are usually reused a lot. So in my opinion the overhead of having a cached method is justified.
The information in basic_data, primitive_block_data and continued_fractions are (in my opinion) not approximately equivalent. We also don't always cache all methods. Instead different cached method have different use cases (but yes there is some hiearchy between them):
(1) If the full block data is needed (not only _primitive_block_data) then the _block_data caching helps. This is a less used case I guess but still the caching helps a lot for that case. Indeed this will also use _primitive_block_data.
(2) If only _primitive_block_data is needed, we don't need to have the _block_data, _primitive_block_data is enough. For instance "hyperbolic binary quadratic forms" are in 11 relation to primitive hyperbolic matrices. So I guess this is the most important case. Also: Indeed _primitive_block_data relies on continued_fraction.
(3) Block decomposition has a rather specific application (basically determining the conjugacy type). We also want to be able to cache continued fraction calculations (in particular since they're probably most costly of the cached methods) without the need to also add unrelated block decomposition calculations and data. So I left the caching for continued_fraction in place. Note that continued fractions are sometimes enough and no primitive block data is needed.
(4) _basic_data is related to the decomposition of the matrix as a product of its generators S, T. it is yet another nonequivalent use case. The whole base code is built on the basic decomposition. For instance it is used to determine if a given matrix even lies in the group. It is used heavily for calculations with modular forms / upper half plane action (to determine the automorphy factor, for calculations involving the fundamental domain or representatives in it). So I decided to always call _basic_data (unless check is disabled in which case nothing is cached by default).
Regarding UniqueRepresentation?: I was just asking about it as an alternative to method caching (I myself also decided against it).
I hope the summary above helped. I understand that you are unhappy with the current implementation. I am not happy about the idea of further removing cached methods (I did some test a while ago: in each case removing a cached method had significant performance impact). But if it is an absolute requirement I would remove the caching for _block_data and _primitive_block_data. As mentioned this will however have a really large negative performance effect on methods that implicitely use them. :(
Is the overhead of an unused cache method so large? If yes, shouldn't the caching mechanism be improved instead?
Regarding the TODO on line 2700: I added it because I am not familiar enough with all facets of the topic (in particular geometry) otherwise I would have improved it. But I know it is of interest to some people. So I guess (unfortunately) nobody will improve it. Maybe the TODO remark should be removed all together since the current documentation seems acceptable.
If the ticket modifications are better "in" than "out" then my suggestion and hope would be to commit something "close" to the current form and to apply more general modifications beyond the scope of just this ticket at a later time (in a different ticket).
Regards
Jonas
comment:26 Changed 6 years ago by
 Commit changed from 3c7ca0f2bf33d3fdec7b79c353b28ccc01cd419d to 0f37005428111c0dfdef6f19e0573a366e9d6270
Branch pushed to git repo; I updated commit sha1. New commits:
0f37005  clarify the usage of cached methods

comment:27 Changed 6 years ago by
 Commit changed from 0f37005428111c0dfdef6f19e0573a366e9d6270 to 9d3bb768b4b65f3a57ff27f3149f94e6abf910a8
Branch pushed to git repo; I updated commit sha1. New commits:
9d3bb76  remove a useless TODO

comment:28 Changed 6 years ago by
 Branch changed from u/jj/triangle_conjugacy to public/16976
 Commit changed from 9d3bb768b4b65f3a57ff27f3149f94e6abf910a8 to 616b0486776cdff54d8653c7bbc52269bd6df44c
Hey Jonas,
1) Do you mind the merge with the latest beta? That will avoid me many recompilations. Otherwise, I can rebase my two commits.
2) I wrote a commit that just clean the code. Nothing big, but a little speed up. Tell me what you think.
3) Concerning the cached_method, I decided to let only two of them (continued_fraction
and _primitive_block_data
) after intensive timings of the doctests. See below. Please tell me if this is really bad.
Potential caching
 continued_fraction
 _block_data
 _primitive_block_data
 primitive_power
 _basic_data
cached methods  time  relative gain 

none  102.0s  
all  57.8 s  43% 
1  75.0 s  26% 
2  79.1 s  22% 
3  82.4 s  17% 
4  88.0 s  13% 
5  98.0 s  4% 
1 + 3  64.2 s  14% (rel to 1) 
2 + 3  76.0 s  4% (rel to 2) 
1 + 2  67.7 s  9% (rel to 1) 
1 + 2 + 3  62.3 s  3% (rel to 1+3) 
So 1+3 is is a 10% lost compared to 1+2+3+4+5... but I would say that removing 3 cached_method is much more!
4) I really do not understand your naming scheme. Why decompose_basic
and not word_decomposition_S_T
or word_S_T
or something that tells you about what it does? The same is true for many methods: _primitive_block_data
, _block_data
, _basic_data
, block_length
, decompose_block
.
5) For some other methods, I was not able to understand what they do... the documentation is by far too short for me. In particular reduced_elements
and simple_elements
.
I am waiting for your comments before going further.
Best Vincent
New commits:
433b9d1  merge 6.5.beta5

f63c738  trac #16976: clean code for Hecke group element

616b048  trac #16976: removed 3 out of 5 @cached_method

comment:29 Changed 6 years ago by
Hey Vincent,
1) I don't mind at all.
2) Thanks a lot. I checked all the changes very closely. They look great! :)
I made some small adjustments:
 For Hecke triangle groups k is usually a rational number, so k = ZZ(k) quite often fails and we want to provide the same exception message
 I pulled the factor ZZ(1) factor out of (Q) again. It produces better looking numerators/denominators and it emphasizes the form resp. sign of the factor.
 I used "u = sum((v[0]1) for v in L)", some authors use "v[0]1" instead of "v[0]" in their definitions, so it feels more natural to me that way.
 For now I added 2 cached_methods back (and ideally I would like to add _block_data too).
3) Thanks for the test, I didn't write mine down unfortunately.
"but I would say that removing 3 cached_method is much more!": Can you maybe elaborate a bit more on the drawbacks/overheads with (unused) cached_methods? How large is the overhead? The tests (in particular interactive usages) seem to only indicate positive effects from caching. I would prefer to keep the cached methods in:
 primitive_power: I would really prefer to keep this a cached_method. It only stores one integer and the calculation of it can be long: Basically the method compares powers of the primitive part against the original matrix until it finds a match. Also that method is reused to e.g. determine if a matrix is primitive. Which is again reused by other functions. Moreover the primitive_power is a number of interest for a given matrix. Caching only occurs if the method is used. In my opinion this is a perfect example of something worthwhile to cache. Also note that most doctests involve only small powers of matrices and there are much slower functions which have more influence on the total time in doctests...
 _basic_data: This method is a candidate to be removed. It is the only cached method which is always called, so disabled caching would reduce the overhead. The calculation of it basically involves determening a representative of a number/matrix in the fundamental domain, which can take very long if the number lies close to "1". So why not cache the result? It is also beeing used for calculations of automorphy factors for modular forms. So if matrices are beeing reused there in modular operations caching could give a big speed up. It's also used for "basic" string representations which is a very good candidate for the default representation of matrices (just saying). So it seems like a waste to compute _basic_data repeatedly (and having to wait for the output). The user experience is improved a lot if he has fast response time to his commands. Without caching "basic" representation might be too "laggy" to use comfortably. Note that when doing calculations one usually uses "basic", "conj" or "block" for representations (so the results can immediately be interpreted). Caching has a large (positive) effect for such calculations. I would keep it in, but yes it's definitely a candidate for removal.
 _block_data: I don't think there are many test cases which reuse block data. If matrices and their block data are beeing reused several times caching might be a big issue. As for _basic_data the user experience with string representations ("conj" or "block") should at least be considered. Again: I would keep it in, but yes it's a candidate for removal.
All in all I also wouldn't neglect the impact on user experience from fast/slow representations. If you insist on removing the cached methods I will accept it however.
4) I tried to improve the wording slightly. "Block length" is a term used in papers.
5) I added more remarks (see is_primitive and is_simple). The terms basically relate
11 to the corresponding terms for the associated fixed points respectively the associated binary quadratic form (at least in the hyperbolic case). The methods reduced_elements resp. simple_elements return all corresponding elements in the conjugacy class of the given element. Ideally those should be member functions for conjugacy classes. But those aren't implemented yet (and probably will never be). :(
Best
Jonas
comment:30 Changed 6 years ago by
 Branch changed from public/16976 to u/jj/triangle_conjugacy
 Commit changed from 616b0486776cdff54d8653c7bbc52269bd6df44c to 9d3bb768b4b65f3a57ff27f3149f94e6abf910a8
 Reviewers set to Vincent Delecroix
 Status changed from needs_info to needs_review
comment:31 Changed 6 years ago by
 Commit changed from 9d3bb768b4b65f3a57ff27f3149f94e6abf910a8 to 67116d50b6a82d826d2d3248b79d2c3a0751177f
Branch pushed to git repo; I updated commit sha1. New commits:
433b9d1  merge 6.5.beta5

f63c738  trac #16976: clean code for Hecke group element

616b048  trac #16976: removed 3 out of 5 @cached_method

67116d5  addressed the review: renamed some functions, added 2 cached_methods back, improved documentation, fixed doctests

comment:32 Changed 6 years ago by
Hi again
I would like to finnish / apply this ticket. If the cached_method are the blocker, what about a compromise: Leave primitive_power as a cached_method but remove _word_S_T_data? If that's still not enough I'm also willing to remove both if it helps to finnish the review.
Best
Jonas
comment:33 Changed 6 years ago by
Hello Jonas,
No. The number of cached_method is not a blocker (let us stick to what we have right now). I want the code to be understandable by me and usable by other people.
Vincent
comment:34 Changed 6 years ago by
 Commit changed from 67116d50b6a82d826d2d3248b79d2c3a0751177f to 9fabb44a5f893dbdcc91e13c818ac8b2b79dbbc0
Branch pushed to git repo; I updated commit sha1. New commits:
9fabb44  improve documentation

comment:35 Changed 6 years ago by
Hi again
Is the code ok now? Or what remains to be done?
Best
Jonas
comment:36 Changed 6 years ago by
 Branch changed from u/jj/triangle_conjugacy to u/vdelecroix/16976
 Commit changed from 9fabb44a5f893dbdcc91e13c818ac8b2b79dbbc0 to 6d7348137d982e27990088f352a5194fd967eefa
 Status changed from needs_review to positive_review
I had to merge with 6.6.beta1 because of a trivial merge conflict due to #17694
You should really think about cleaning before implementing anything else. I already made many remarks about that are here are more:
 The code of
MatrixGroupElement
is done in such way that there is no need to write a custom__init__
. You only need to implement a._matrix_check
in the parent.
 There is a
.gitignore
file insage/modular/modform_hecketriangle/
because ofcommit c8cbd7acfc81bdc1c24684f26d986f59491e0a3a Author: Martin Raum <martin@raumbrothers.eu> Date: Thu May 8 16:32:54 2014 +0200 Rename folder for Hecke triangle modforms.
Vincent
New commits:
6d73481  merge sage6.6.beta1 in #16976

comment:37 Changed 6 years ago by
 Branch changed from u/vdelecroix/16976 to u/jj/triangle_conjugacy
 Commit changed from 6d7348137d982e27990088f352a5194fd967eefa to 7dcee3441862c9af9f1a63e1c3c8d4b957d2d705
New commits:
7dcee34  remove .gitignore, add further explanations on __init__, change ValueError to TypeError for element checks

comment:38 Changed 6 years ago by
 Milestone changed from sage6.5 to sage6.6
comment:39 Changed 6 years ago by
 Branch changed from u/jj/triangle_conjugacy to 7dcee3441862c9af9f1a63e1c3c8d4b957d2d705
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Rename "forms" to "elements"