Finitely presented modules over the Steenrod algebra
catanzaromj opened this issue · 207 comments
This package implements finitely presented modules over the mod p Steenrod algebra. We define classes for such finitely presented modules, their elements, and morphisms between them. Methods are provided for doing some homological algebra, e.g., computing kernels and images of morphisms, and finding free resolutions of modules.
Depends on #32505
Depends on #33275
Depends on #33323
CC: @sverre320 @sagetrac-kvanwoerden @jhpalmieri @tscrim @rrbruner @cnassau
Component: algebra
Keywords: Steenrod algebra, modules, homological algebra
Author: Bob Bruner, Michael Catanzaro, Sverre Lunøe-Nielsen, Koen van Woerden
Branch/Commit: 7035ae5
Reviewer: John Palmieri, Travis Scrimshaw
Issue created by migration from https://trac.sagemath.org/ticket/30680
Author: Bob Bruner, Michael Catanzaro, Sverre Lunøe-Nielsen, Koen van Woerden
Changed branch from u/gh-catanzaromj/finitely_presented_modules_over_the_steenrod_algebra to none
Changed keywords from none to Steenrod algebra, modules, homological algebra
Description changed:
---
+++
@@ -1 +1,5 @@
+This package implements finitely presented modules over the mod p Steenrod algebra. We define classes for such finitely presented modules, their elements, and morphisms between them. Methods are provided for doing some homological algebra, e.g., computing kernels and images of morphisms, and finding free resolutions of modules.
+**An example**
+
+Description changed:
---
+++
@@ -1,5 +1,2 @@
This package implements finitely presented modules over the mod p Steenrod algebra. We define classes for such finitely presented modules, their elements, and morphisms between them. Methods are provided for doing some homological algebra, e.g., computing kernels and images of morphisms, and finding free resolutions of modules.
-**An example**
-
-Commit: cc69ed5
Branch pushed to git repo; I updated commit sha1. New commits:
81fb0c1 | Replace `_cmp_` with _richcmp_ |
This is quite a project and looks good on a first lookover. Thank you for the contribution. I have some immediate questions/comments before delving too much into the code:
- Could this be split up into smaller tickets? This would make the review much easier.
- I think you could rename
finitely_presented_over_the_steenrod_algebratofp_over_steenrod_algebrain order to make the file paths shorter to type. - I think the module elements should be Cythonized as this is generally where the majority of the computations happen and it is good to be faster here.
- Use the Sage default latex commands of
\ZZ,\GF{p}, etc. so the documentation is standardized. - Check your use of
::and:. If there is going to be a docstring after, then it should be::, otherwise it should be:(with exceptions for, e.g.,.. NOTE::). - Errors should be of the form
raise TypeError("a message without a capital letter or period")to follow Python's conventions. Also, you should not raise aRuntimeErrorunless you have a very good reason to;NotImplementedError,TypeError, andValueErrorare usually much better. - I think it is better to have class level documentation explaining stuff about input, descriptive information, and use-case doctests. The
__init__can then have a simple docstring with a test that basically doesTestSuite(foo).run(). This is also a common pattern in Sage.
tscrim,
Thanks for the quick follow-up. Here are some preliminary answers:
-
There are (essentially) three new classes introduced in this ticket:
a) free graded modules over F_p-algebras
b) f.p. graded modules over F_p-algebras, and
c) f.p. graded modules over the Steenrod algebra.The class structure is so that f.p. modules (b) have a morphism of free modules (a) as internal data to represent the finite presentation of itself, while a f.p. module over the Steenrod algebra (c) is derived from the class b).
It would be possible to split the ticket into perhaps two or three tickets: either a), b) and c), or a)+b) and c). The classes in (b) contain all the functionality which does not depend on features special for the Steenrod algebra. Thus, they might be of more general interest.
However, as they are written, classes a)+b) are privately used by c) and was not intended for public use (yet). As a consequence, the examples and tests in a) + b) only consider modules over the Steenrod algebra.
-
Indeed there are performance bottlenecks here. In particular, a lot of time is spent just creating instances of the free modules (class a mentioned above). The current implementation was motivated by readability, and a performance optimization was planned as a second step. Preliminary measurements indicate that even a Python version using tighter data structures would increase performance by x10 already.
However -- we have not considered Cython because neither of us have used it before. This may be the best option though, and I am looking into it now. One concern I have is that we use derived classes (fpa modules are e.g. derived from fp modules). Would this complicate using Cython, in your opinion?
Thanks for your input so far. These are certainly valid points. There should be an update addressing 2. 4. 5. 6. and 7. coming soon.
-
It actually would be better to run the tests on the classes themselves rather than through an intermediary because it makes errors easier to find. You will just have to import the relevant classes in each of the doctests.
-
I would look more to optimization before accepting this. This first version is good for setting up the testing and code framework, but 10x is a huge gain and worth doing before merging it into Sage IMO. Using Cython shouldn't complicate things too much if you only have single inheritance. However, the main things you should use Cython on are the element classes (not the parents, which usually have multiple inheritance because you want them to also inherit from
UniqueRepresentation) and time-critical computations. I am happy to help in translating things into Cython too.
Branch pushed to git repo; I updated commit sha1. New commits:
fbe9446 | Bugfix. |
74ff9e4 | Renamed project directory. |
d115e0c | Use standard Sage latex macros. |
21c5995 | Double :'s when docstring is wanted. |
064e085 | Standardized error messages |
bd8697c | Moved docstring from `__init__` to class doc. |
de83eea | Made import paths relative |
Performance of the original Python code.
Attachment: python_perf_res.csv.gz
Performance of the cythonized code.
Attachment: cython_perf_res.csv.gz
Attachment: perf.png
visualization of the performance data combined
visualization of total time (green colors) and accounted time (red colors) for both python and cythonized code.
Attachment: perf_accounted_time.png
Visualization of performance data where only time spent in external modules are shown
Attachment: perf_comp.png
Attachment: perf_cython.png
Visualization of performance data for cython code only.
Visualization of performance data for python code only.
Attachment: perf_python.png
We have pushed updates to this package which addresses tscrim's above comments 2, 4, 5, 6, and 7.
With regards to comment 3, we have tried to use Cython to optimize certain parts of the package but without experiencing any significant speedups. I commented earlier that
"Preliminary measurements indicate that even a Python version using tighter data structures would increase performance by x10 already." Unfortunately, this comment was based on a too simple example (constructing a free module on one generator). The performance tests we now have conducted are based on a real world use case which is much more relevant for the typical user.
We have therefore come to the conclusion that we want to keep the code as it is, all in Python.
We have conducted performance measurements of both the original Python code as well as a version of it using Cython. Our analysis points to two facts:
-
There is virtually no difference in computing time when comparing our original all-Python code to a version where fp_element.py and free_element.py have been turned into .pyx-files and "cythonized".
-
Approximately 70% of the time used computing the resolution is spent in either the SteenrodAlgebra module or doing linear algebra (subspace spanning, vector space quotients, etc.) These are modules that are external to our package, so Cythonizing our code will not have an effect on this chunk of time. We stopped looking when we could account for 70%-80% of the time consumed, and we are certain that we are not spending the remaining time in a loop somewhere which can benefit from Cythonizing. We imagine various memory allocations and overhead due to the dynamic nature of Python accounts for at least some of the remaining 30%.
The code to reproduce these performance measurements is available in the
two experimental branches:
origin/u/gh-sverre320/fp_over_steenrod_algebra_cython_test
origin/u/gh-sverre320/fp_over_steenrod_algebra_performance_test
The first branch contains a version of our package where the two modules fp_element.py and free_element.py have been turned into .pyx-files and "cythonized".
Both branches contain a sage script called 'performance_test.sage' which run the same performance test. It can be used like this:
> ./sage performance_test.sage
The test produces a CSV formatted output, and we have included the results from running it on our system to this comment.
Here's a quick explanation of their contents:
The output is CSV-formatted and measures how much time various parts of the code spends during the computation of one (homological) step of a certain free resolution. This computation is done one (internal) degree at a time, and each line in the CSV file corresponds to a single degree.
Each row contains the following measurements:
"total time": This is the number of seconds it takes to complete one step of the free resolution in one homogeneous degree.
"accounted time": The number of seconds which are accounted for (We only measured the time spent in certain parts which we suspected were most time consuming).
"SteenrodAlgebra": The number of seconds spent calling the SteenrodAlgebra module.
"linear algebra": The number of seconds spent running external linear algebra code.
For each line, the two last values should add up to "accounted time" (or close to it. We left out some more measurements which were tiny in comparison to the two already mentioned.)
The attached images visualize these data.
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
Sorry for the massive delay in getting back to this.
Thank you for looking into Cythonization. I would have thought there would be more of an advantage going to/from the linear algebra in Sage than dealing with the Steenrod algebra from a quick look through the code.
I have some quick comments before going into a deeper review:
It should be INPUT: and OUTPUT: with single quotes. If there is code afterwards (such as Sage doctests, which are indented one level), then it should be EXAMPLES:: and TESTS::.
Every method needs a doctest. Good ones for __init__ are to create an instance foo and run TestSuite(foo).run().
The author bullet points should not be indented.
Input items should not end is a period/full-stop.
For _richcmp_, it is already guaranteed the elements have the same parent.
I would not do an import at the class level (see from .fp_element import FP_Element), but instead at the module level.
I would set ModuleClass and HomSpaceClass at the class level rather than during the __init__.
Do you want j to be a public attribute of FP_Module? If so (which I don't think is a good idea though), it needs a better name.
The name FP_Module doesn't follow Python naming conventions. Also, it is a bit too generic IMO.
You should add a method for creating the modules to the Steenrod algebra so it is both more discoverable and natural for the user.
I will likely have more comments later as I go deeper into the code.
Perhaps needless to mention, but Cython gets you big speedups only with some care, i.e. you'd need to avoid using Python types (anything untyped in Cython code would be Python, and may render the effort of cythonising useless).
tscrim: Great, you're back!
The name FP_Module doesn't follow Python naming conventions. Also, it is a bit too generic IMO.
About the naming, we have struggled a bit in the past getting names for these classes. They tend to grow rather long when we put in too many descriptive words.
But could this work?
FP_Module -> FinitelyPresentedModule
FPA_Module -> FinitelyPresentedSteenrodAlgebraModule
Personally, if we are to make the class names more descriptive, I would prefer to go all the way, like so:
FP_Module -> FinitelyPresentedModule
FPA_Module -> FinitelyPresentedModuleOverTheSteenrodAlgebra
Also, what about directory path names, does this mean that they have to grow too?
dimpase: Yes, that makes sense. Also, since the performance analysis points to the fact that most of the heavy lifting is performed by other libraries, I saw no point in optimizing our internal data structures.
I have some more consecutitive free time now to devote to a larger patch review. Sorry again for taking so long to get to it.
I would suggest the folder being fp_steenrod_repr the files being fp_graded_* and gp_steenrod_* and the classes being FinitelyPresentedGradedAlgebraModule and FinitelyPresentedSteenrodRepresentation. Shortening FinitelyPresented to FP is also good, but no underscore _ after it.
If the FP_Module is really more general, then the elements should be Cythonized and put in a different folder. I think it would be good if the corresponding documentation stated a bit about what assumptions you have on the algebra's implementation.
In the morphism implementation, you should instead implement the single underscore version of the algebraic operations, e.g. _add_. Then you can assume compatible maps (in terms of domain and codomain) as the coercion framework will take care of the rest.
Do you need the implementation of free modules? In particular, I am wondering if you could use what is currently in Sage (with perhaps some renaming of methods and/or adding stuff to an appropriate category)?
Setting a new milestone for this ticket based on a cursory review.
Here is a small patch. It fixes some documentation syntax, and it also moves the documentation from "algebras" to "modules". It fixes two doctest failures, probably due to a change in another component of Sage.
Last 10 new commits:
4d15e87 | Replace overset with xrightarrow and remove unused imports |
8febd53 | Remove additional unused imports |
a13d0f6 | Bugfix. |
c1a84da | Renamed project directory. |
ff32fa2 | Use standard Sage latex macros. |
bc3516b | Double :'s when docstring is wanted. |
723ce71 | Standardized error messages |
848bd91 | Moved docstring from `__init__` to class doc. |
4c920c8 | Made import paths relative |
6a617ff | trac 30680: fix docstrings, move documentation from "algebras" to "modules" |
I also echo tscrim's comments. For example, the module sage.combinat.free_module is may be a good replacement for your free module implementation, or a good class to use for inheritance (where you might add generator_degrees, etc.).
Using long names (like FinitelyPresentedGradedAlgebraModule or FPGradedAlgebraModule) is pretty typical in Sage, and it's typically not a burden because you either don't need to type the name much or when you do, then at least in an interactive session, you can use tab completion. So the preference is to use more descriptive names.
The function mod_p_log can be replaced by the method exact_log (defined for Sage Integers).
Actually, mod_p_log(a, p) is 1+a.exact_log(p). Here is a potential patch:
diff --git a/src/sage/modules/fp_over_steenrod_algebra/profile.py b/src/sage/modules/fp_over_steenrod_algebra/profile.py
index 95f8277e1c..a12b454c40 100755
--- a/src/sage/modules/fp_over_steenrod_algebra/profile.py
+++ b/src/sage/modules/fp_over_steenrod_algebra/profile.py
@@ -37,32 +37,7 @@ from sage.algebras.steenrod.steenrod_algebra import SteenrodAlgebra
from copy import copy
-#import sage.modules.fp_over_steenrod_algebra.utility as Utility
-def mod_p_log(n,p):
- r"""
- Input an integer $n$ and a prime $p$
- Output the $k$ so that $p^{k-1} < n <= p^k$
-
- EXAMPLES::
-
- sage: from sage.modules.fp_over_steenrod_algebra.profile import *
- sage: mod_p_log(1,4)
- 1
- sage: mod_p_log(8,3)
- 2
- sage: mod_p_log(9,3)
- 3
-
- """
- k=0
- pow=1
- while n >= pow:
- k += 1
- pow *= p
- return k
-
-
-def profile_ele(alist,char=2):
+def profile_ele(alist, char=2):
"""
Finds the smallest sub-Hopf algebra containing the element passed.
`alist' is assumed to be an element of the Steenrod Algebra, (the only other
@@ -91,32 +66,33 @@ def profile_ele(alist,char=2):
alist2 = [e[0] for e in alist]
maxlength = max([0]+[len(e) for e in alist2])
alist2 = [list(e) + (maxlength-len(e))*[0] for e in alist2]
- minprofile = [max([alist2[i][j] for i in range(len(alist2))]) \
+ minprofile = [max([alist2[i][j] for i in range(len(alist2))])
for j in range(maxlength)]
- minprofile = tuple(map(lambda xx: mod_p_log(xx,char),minprofile))
+ minprofile = tuple(map(lambda xx: xx.exact_log(char)+1, minprofile))
return find_min_profile(minprofile,char)
- if char != 2:
- alistQ = [e[0][0] for e in alist]
- alistP = [e[0][1] for e in alist]
- maxlengthQ = max([0]+[len(e) for e in alistQ])
- maxlengthP = max([0]+[len(e) for e in alistP])
- alistQ = [list(e) + (maxlengthQ-len(e))*[0] for e in alistQ]
- alistP = [list(e) + (maxlengthP-len(e))*[0] for e in alistP]
- minprofileQ = [max([alistQ[i][j] for i in range(len(alistQ))]) \
- for j in range(maxlengthQ)]
- minprofileP = [max([alistP[i][j] for i in range(len(alistP))]) \
- for j in range(maxlengthP)]
- minprofileP = tuple(map(lambda xx: mod_p_log(xx,char),minprofileP))
- if not minprofileQ:
- minpQ=[]
- else:
- minpQ = [1]*(max(minprofileQ)+1)
- for j in minprofileQ:
- minpQ[j] = 2
- return find_min_profile((minprofileP,minpQ),char=char)
+
+ # odd primes
+ alistQ = [e[0][0] for e in alist]
+ alistP = [e[0][1] for e in alist]
+ maxlengthQ = max([0]+[len(e) for e in alistQ])
+ maxlengthP = max([0]+[len(e) for e in alistP])
+ alistQ = [list(e) + (maxlengthQ-len(e))*[0] for e in alistQ]
+ alistP = [list(e) + (maxlengthP-len(e))*[0] for e in alistP]
+ minprofileQ = [max([alistQ[i][j] for i in range(len(alistQ))])
+ for j in range(maxlengthQ)]
+ minprofileP = [max([alistP[i][j] for i in range(len(alistP))])
+ for j in range(maxlengthP)]
+ minprofileP = tuple(map(lambda xx: xx.exact_log(char)+1, minprofileP))
+ if not minprofileQ:
+ minpQ=[]
+ else:
+ minpQ = [1]*(max(minprofileQ)+1)
+ for j in minprofileQ:
+ minpQ[j] = 2
+ return find_min_profile((minprofileP,minpQ),char=char)
-def enveloping_profile_elements(alist,char=2):
+def enveloping_profile_elements(alist, char=2):
"""
Finds the profile function for the smallest sub-Hopf algebra containing
the list of elements passed. Entries of `alist' are elements of the Steenrod
@@ -145,26 +121,27 @@ def enveloping_profile_elements(alist,char=2):
return (0,)
maxlength = max([len(e) for e in alist2])
alist2 = [list(e) + (maxlength-len(e))*[0] for e in alist2]
- minprofile = tuple(max([alist2[i][j] for i in range(len(alist2))]) \
+ minprofile = tuple(max([alist2[i][j] for i in range(len(alist2))])
for j in range(maxlength))
return find_min_profile(minprofile)
- else:
- masterlist = [profile_ele(x,char) for x in alist if x != 0]
- alistP = [x[0] for x in masterlist]
- alistQ = [x[1] for x in masterlist]
- if not alistP and not alistQ:
- return ((0,),(0,))
- maxlengthQ = max([len(e) for e in alistQ])
- maxlengthP = max([len(e) for e in alistP])
- alistQ = [list(e) + (maxlengthQ-len(e))*[0] for e in alistQ]
- alistP = [list(e) + (maxlengthP-len(e))*[0] for e in alistP]
- minprofileQ = tuple(max([alistQ[i][j] for i in range(len(alistQ))]) \
- for j in range(maxlengthQ))
- minprofileP = tuple(max([alistP[i][j] for i in range(len(alistP))])\
- for j in range(maxlengthP))
- return find_min_profile((minprofileP,minprofileQ),char=char)
-
-def enveloping_profile_profiles(alist,char=2):
+
+ # odd primes
+ masterlist = [profile_ele(x,char) for x in alist if x != 0]
+ alistP = [x[0] for x in masterlist]
+ alistQ = [x[1] for x in masterlist]
+ if not alistP and not alistQ:
+ return ((0,),(0,))
+ maxlengthQ = max([len(e) for e in alistQ])
+ maxlengthP = max([len(e) for e in alistP])
+ alistQ = [list(e) + (maxlengthQ-len(e))*[0] for e in alistQ]
+ alistP = [list(e) + (maxlengthP-len(e))*[0] for e in alistP]
+ minprofileQ = tuple(max([alistQ[i][j] for i in range(len(alistQ))])
+ for j in range(maxlengthQ))
+ minprofileP = tuple(max([alistP[i][j] for i in range(len(alistP))])
+ for j in range(maxlengthP))
+ return find_min_profile((minprofileP,minprofileQ),char=char)
+
+def enveloping_profile_profiles(alist, char=2):
"""
Finds the profile function for the smallest sub-Hopf algebra containing
the sub-algebras corresponding the list of profile functions passed. Accepts
@@ -190,24 +167,25 @@ def enveloping_profile_profiles(alist,char=2):
alist2 = list(copy(alist))
maxlength = max([len(e) for e in alist2])
alist2 = [list(e) + (maxlength-len(e))*[0] for e in alist2]
- minprofile = tuple(max([alist2[i][j] for i in range(len(alist2))]) \
+ minprofile = tuple(max([alist2[i][j] for i in range(len(alist2))])
for j in range(maxlength))
return find_min_profile(minprofile)
- else:
- alistP = [copy(alist[i][0]) for i in range(len(alist))]
- alistQ = [copy(alist[i][1]) for i in range(len(alist))]
- maxlengthQ = max([len(e) for e in alistQ])
- maxlengthP = max([len(e) for e in alistP])
- alistQ = [list(e) + (maxlengthQ-len(e))*[0] for e in alistQ]
- alistP = [list(e) + (maxlengthP-len(e))*[0] for e in alistP]
- minprofileQ = tuple(max([alistQ[i][j] for i in range(len(alistQ))]) \
- for j in range(maxlengthQ))
- minprofileP = tuple(max([alistP[i][j] for i in range(len(alistP))]) \
- for j in range(maxlengthP))
- return find_min_profile((minprofileP,minprofileQ),char=char)
-
-
-def valid(LL,char=2):
+
+ # odd primes
+ alistP = [copy(alist[i][0]) for i in range(len(alist))]
+ alistQ = [copy(alist[i][1]) for i in range(len(alist))]
+ maxlengthQ = max([len(e) for e in alistQ])
+ maxlengthP = max([len(e) for e in alistP])
+ alistQ = [list(e) + (maxlengthQ-len(e))*[0] for e in alistQ]
+ alistP = [list(e) + (maxlengthP-len(e))*[0] for e in alistP]
+ minprofileQ = tuple(max([alistQ[i][j] for i in range(len(alistQ))])
+ for j in range(maxlengthQ))
+ minprofileP = tuple(max([alistP[i][j] for i in range(len(alistP))])
+ for j in range(maxlengthP))
+ return find_min_profile((minprofileP,minprofileQ),char=char)
+
+
+def valid(LL, char=2):
"""
Determines if the list passed is a valid profile.
## When checking at odd primes, the `P`-part must be the 0th entry in LL,
@@ -235,20 +213,21 @@ def valid(LL,char=2):
for i in range(1,r):
value = value and ((L[r] >= L[r-i] - i) or (L[r] >= L[i]))
return value
- else:
- (alistP,alistQ) = (LL[0],LL[1])
- M = [0] + list(alistP) + [0]*len(alistP)
- L = list(alistQ) + [1]*(len(alistQ)+1)
- M = M + [0]*abs(len(M)-len(L)) # Pad so they're the same length
- L = L + [1]*abs(len(M)-len(L))
- value = valid(alistP,char=2) # P part must satisfy same conditions, regardless of prime.
- for r in range(len(L)): # \tau's indexed at 0, unlike \xi 's
- if (L[r] == 1) and value:
- for i in range(r+1):
- value = value and ((M[i] <= r -i) or (L[r-i] == 1))
- return value
-def nextprof(p,n,char=2):
+ # odd primes
+ (alistP,alistQ) = (LL[0],LL[1])
+ M = [0] + list(alistP) + [0]*len(alistP)
+ L = list(alistQ) + [1]*(len(alistQ)+1)
+ M = M + [0]*abs(len(M)-len(L)) # Pad so they're the same length
+ L = L + [1]*abs(len(M)-len(L))
+ value = valid(alistP,char=2) # P part must satisfy same conditions, regardless of prime.
+ for r in range(len(L)): # \tau's indexed at 0, unlike \xi 's
+ if (L[r] == 1) and value:
+ for i in range(r+1):
+ value = value and ((M[i] <= r -i) or (L[r-i] == 1))
+ return value
+
+def nextprof(p, n, char=2):
"""
Takes a possible profile `p' and a base profile `n'. Returns the next
profile in lexicographic order. After all valid profiles `p' of
@@ -292,22 +271,23 @@ def nextprof(p,n,char=2):
else: # inside n still, so reset to n
p[i] = n[i]
return n + [0]*(len(p)-len(n)) + [1] # fell off the end
- else: # odd primes
- pQ = list(p[1])
- nQ = list(n[1])
- for i in range(len(pQ)):
- if pQ[i] < 2:
- pQ[i] += 1
- return pQ
+
+ # odd primes
+ pQ = list(p[1])
+ nQ = list(n[1])
+ for i in range(len(pQ)):
+ if pQ[i] < 2:
+ pQ[i] += 1
+ return pQ
+ else:
+ if i > len(nQ) -1:
+ pQ[i] = 1
else:
- if i > len(nQ) -1:
- pQ[i] = 1
- else:
- pQ[i] = nQ[i]
- return nQ + [1]*(len(pQ)-len(nQ)) +[1]
+ pQ[i] = nQ[i]
+ return nQ + [1]*(len(pQ)-len(nQ)) +[1]
-def find_min_profile(prof,char=2):
+def find_min_profile(prof, char=2):
"""
Given a tuple of integers (a pseudo-profile), this function will
output the smallest legal profile function containing it. This
@@ -346,11 +326,11 @@ def find_min_profile(prof,char=2):
while not valid(p,char):
p = nextprof(p,n,char)
return tuple(p)
- else:
- pP,pQ = list(prof[0]), list(prof[1])
- P = find_min_profile(pP,char=2)
- Q = copy(pQ)
- while not valid([P,Q],char):
- Q = nextprof([P,Q],[P,pQ],char)
- return (P,Q)
+
+ pP,pQ = list(prof[0]), list(prof[1])
+ P = find_min_profile(pP,char=2)
+ Q = copy(pQ)
+ while not valid([P,Q],char):
+ Q = nextprof([P,Q],[P,pQ],char)
+ return (P,Q)
Thanks for making concrete suggestions, like using sage.combinat.free_module. I am just not sure it's worth it. When I look at the existing code, I see a lot of reference to the degree of elements. All that code has to be put back into the class that inherits from combinat (which has no concept of gradings). And so I am not convinced it's going to be saving a lot of lines of code in the end.
I think of the free module class as part of the private implementation of this package, and not an addition to Sage in itself. Replacing it or letting it inherit from combinat would have implications on the rest of the code. Since these kinds of changes usually take longer to implement than what one usually expects, I am hesitant about trying this out.
Am I just being too negative here, or are there any obvious benefits I am missing?
Well, I find it annoying that there are two different implementations of free modules already, and adding another would only add to that. In general, the pieces of Sage should build on each other, rather than each developer building their own version of each thing they want.
When I first wrote the chain complex and simplicial complex code in Sage, I used the existing code for matrices and linear algebra (for the boundary maps), and as a result, I found a bunch of bugs in that code. The more the pieces of Sage are tied together, the stronger the pieces are, because they're used and tested in more different ways.
I will try to take a look to see how much work would need to be done to have your code inherit from sage.combinat.free_module.
maybe sage.combinat.free_module ought to be extended to accommodate for the needs of this ticket?
I find it surprising that
sage.combinat.free_module has no concept of grading.
Back when I started refactoring the original code for this package, I tried to find a suitable class to build (free) graded modules on. I failed to find one, and decided to write my own and make it an internal component of this package.
However, @jhpalmieri, I absolutely agree with what you are saying: Ideally, I would have liked to open a separate ticket with the goal of adding a more general class for free graded modules.
This seemed to me like a bigger task, and so I compromised. It's a task I necessarily cannot do myself, as there are many opinions about what a graded module should be. It is e.g. not clear to me that a class for representing free graded modules should inherit from the ungraded module class. For example, I guess this relates directly to the question about allowing sums of elements of different degrees or not.
One option for the current ticket has always been to integrate the free module code into the class of the finitely presented modules (FP_xxx) and avoid the problem we are facing now. However, it always made much more sense to me, in terms of code readability, to separate the code for free module representation.
So to conclude: If we to open a ticket and do graded modules in Sage correctly, I am willing to help out. Otherwise, I suggest we accept the solution in this ticket and postpone the cleanup.
Of course, if I am wrong and this
I will try to take a look to see how much work would need to be done
to have your code inherit from sage.combinat.free_module.
turns out to make more sense, I am happy to take this path.
My current plan is the following, time-permitting:
- move the files
fp_...into a new directorysage/modules/fp_graded/, in the hopes that they will be of more general use. - rewrite those files to base them on existing free module implementations.
- then see what's left after that.
I think this fits into tscrim's suggestion. Assuming there are no objections, then once I've made some progress, I will open a ticket for general finitely presented graded modules over graded rings, and we can rebase this ticket on top of that one.
By the way, I don't see any reason to forbid sums of elements of different degrees; people can decide depending on their uses. It's unusual but not unheard of for the Steenrod algebra, and someone might try something strange and make a great new discovery.
I have questions and comments:
-
first, in other parts of Sage that use gradings, the zero element has no degree, and in fact
zero.degree()raises an error rather than returningNoneas it does here. So I am changing the behavior here to raise an error. -
I'm not sure what to do with homsets and morphisms. Some people would insist that
Hom(M, N)should contain only degree 0 maps; others (especially in algebraic topology, in my experience) allow maps of any degree. (Fortunately no one allows maps that do not preserve degrees, when considering categories of graded modules.) How do we handle this? Should there be two different structures, one for degree 0 maps, one for maps of arbitrary degree? Or just degree 0 maps, and then people can considerHom(Sigma^i M, Sigma N)if they want maps of degreeifromMtoN?
This may be more a question for Travis. Should the category be GradedModules or GradedModulesWithBasis? Maybe if we're working over an algebra with a distinguished basis, the module should inherit that basis, at least in the case of a free module. I'm not sure, though, and I really don't know what to do about non-free modules. (I haven't gotten that far in my modifications: I've just been dealing with free modules.)
I'm a little puzzled by the category setup in this context. Does "with basis" refer to a basis over the algebra over which we're working, or over the base field for that algebra? Consider this:
sage: R.<x> = QQ[]
sage: R
Univariate Polynomial Ring in x over Rational Field
sage: M = FreeModule(R, ['a', 'b'])
sage: M.category()
Category of finite dimensional modules with basis over Univariate Polynomial Ring in x over Rational Field
The "finite dimensional" part of that sounds odd unless you interpret it as meaning "free and finitely generated".
sage: M.basis()
Finite family {'a': B['a'], 'b': B['b']}
So this is viewing the basis as being over the polynomial ring.
On the other hand:
sage: A = GradedModulesWithBasis(QQ).example()
sage: A
An example of a graded module with basis: the free module on partitions over Rational Field
sage: A.homogeneous_component_basis(4)
Lazy family (Term map from Partitions to An example of a graded module with basis: the free module on partitions over Rational Field(i))_{i in Partitions of the integer 4}
sage: list(A.homogeneous_component_basis(4))
[P[4], P[3, 1], P[2, 2], P[2, 1, 1], P[1, 1, 1, 1]]
So homogeneous_component_basis(...) allows access to the vector space basis.
It looks like "with basis" means over the ring or algebra connected to the module, not the ground field. So maybe it should be in the categories
GradedModulesWithBasis(A)only in the case of free modulesGradedModulesWithBasis(A.base_ring())for all modules, assuming we can determine a basis of each homogeneous piece, and this should be possible as long as the algebra has a distinguished basis.
Does that make sense?
@jhpalmieri: I think your plan is perfect, and totally in tune with what I hoped could be done. (I even think there is a comment about this in the beginning of fp_module.py.)
At any rate, I am happy about this turn and would gladly help out if I can.
For degrees of morphisms, I propose:
- we allow construction of morphisms of any degree, but
- Hom(M,N) should consist only of morphisms of degree 0.
Comments?
Replying to @jhpalmieri:
For degrees of morphisms, I propose:
- we allow construction of morphisms of any degree, but
- Hom(M,N) should consist only of morphisms of degree 0.
Comments?
If Hom(M,N) is to contain morphisms of any degree, then it should be a graded vector space, and would not be of finite type, in general. This suggests Hom(M,N) should contain morphisms of degree 0 only.
Counter-argument: a cochain representing an element of Exts,t(M,N) is a homomorphism of degree t from M s (the sth stage in your free resolution of M) to N, or a homomorphism of degree 0 from M_s to \Sigmat N. Then, lifting this to a chain map, you'll need degree 0 morphisms from M{s+i} to \Sigmat N_i (where N_* is your resolution of N).
You end up needing to construct all (well, many of) the suspensions of every term in any resolution you create, which seems to be a lot of extra baggage. Morphisms of any degree obviate this.
If you have morphisms of any degree, but Hom(M,N) only includes those of degree 0, where do the others live?
Yesterday I browsed the internet, and a majority of places viewed Hom as containing only degree 0 maps. This agrees with my impression that many people view the category of graded modules as having degree 0 maps as the morphisms.
I think that computationally, constructing a suspension of a graded module should not be a burden. On the other hand, inheriting from UniqueRepresentation may mean that Sage will never truly forget a graded module once it's been constructed, so maybe constructing lots of suspensions would be a burden. If this becomes a concern, we can create a new class for the suspension of a module: the input would be an already existing module (no new resources required there) and an integer.
By the way, if we wanted separate classes for degree zero maps and maps of arbitrary degree, then vector_presentation would make sense for the zero map in the degree zero case: you would just get the zero matrix of the appropriate size.
A more practical question: if we don't allow maps of nonzero degree in Hom, then how do we construct maps? Currently the easiest way to construct them is Hom(M,N)(...values...), but that won't work if we change Hom. Hom does take an extra argument, category, so we could use a different category to allow nonzero degree maps, although I'm not sure what that category should be called.
Replying to @dimpase:
maybe
sage.combinat.free_moduleought to be extended to accommodate for the needs of this ticket?
+1 and we can likely use a lot of the stuff from the category, which means just implementing stuff at the parent level. It might be a bit slower than directly implementing it, but it might not be the bottleneck.
I find it surprising that
sage.combinat.free_modulehas no concept of grading.
It is all in the category, which get then you implement for the corresponding parent. Perhaps we could extend CFM that takes an optional grading parameter, but so far, every use-case of this required us to subclass for other functionality too.
Replying to @tscrim:
Replying to @dimpase:
maybe
sage.combinat.free_moduleought to be extended to accommodate for the needs of this ticket?+1 and we can likely use a lot of the stuff from the category, which means just implementing stuff at the parent level. It might be a bit slower than directly implementing it, but it might not be the bottleneck.
Although CombinatorialFreeModule is not exactly right for the modules here. At least in the free module case (which is as far as I've gotten), you only care about the degrees of the generators, you don't want to give them names, so there is no named basis. A typical element is listed as <a1, a2, ...> which means the sum of a_i * generator_i, and this looks like a pretty efficient way to describe elements. We could create names, but they would be artificial.
Note that sage.modules.free_module is not suited for this, either: if you try to use it to create a free module over, say, the Steenrod algebra, you get
UserWarning: You are constructing a free module
over a noncommutative ring. Sage does not have a concept
of left/right and both sided modules, so be careful.
It's also not guaranteed that all multiplications are
done from the right side.
I find it surprising that
sage.combinat.free_modulehas no concept of grading.It is all in the category, which get then you implement for the corresponding parent. Perhaps we could extend CFM that takes an optional
gradingparameter, but so far, every use-case of this required us to subclass for other functionality too.
Replying to @jhpalmieri:
This may be more a question for Travis. Should the category be
GradedModulesorGradedModulesWithBasis?
If there is a distinguished basis for the module, then GradedModulesWithBasis. Otherwise just GradedModules.
Maybe if we're working over an algebra with a distinguished basis, the module should inherit that basis, at least in the case of a free module.
I would think that depends on the construction. However, having a distinguished basis means you can do linear algebra, which gives you a lot more functionality.
I'm not sure, though, and I really don't know what to do about non-free modules. (I haven't gotten that far in my modifications: I've just been dealing with free modules.)
Since we don't have much if any support for nonfree modules in Sage, you are out there on your own to figure out what the best practice should be.
I'm a little puzzled by the category setup in this context. Does "with basis" refer to a basis over the algebra over which we're working, or over the base field for that algebra? Consider this:
sage: R.<x> = QQ[] sage: R Univariate Polynomial Ring in x over Rational Field sage: M = FreeModule(R, ['a', 'b']) sage: M.category() Category of finite dimensional modules with basis over Univariate Polynomial Ring in x over Rational FieldThe "finite dimensional" part of that sounds odd unless you interpret it as meaning "free and finitely generated".
Perhaps it would be a bit better to call it the category of "finite rank free modules", but that is something you are best discussing with Nicholas about.
sage: M.basis() Finite family {'a': B['a'], 'b': B['b']}So this is viewing the basis as being over the polynomial ring.
Agreed.
On the other hand:
sage: A = GradedModulesWithBasis(QQ).example() sage: A An example of a graded module with basis: the free module on partitions over Rational Field sage: A.homogeneous_component_basis(4) Lazy family (Term map from Partitions to An example of a graded module with basis: the free module on partitions over Rational Field(i))_{i in Partitions of the integer 4} sage: list(A.homogeneous_component_basis(4)) [P[4], P[3, 1], P[2, 2], P[2, 1, 1], P[1, 1, 1, 1]]So
homogeneous_component_basis(...)allows access to the vector space basis.It looks like "with basis" means over the ring or algebra connected to the module, not the ground field.
Yes, that is correct, it is the base ring R, not any underlying ground ring/field that might be used to construct R.
So maybe it should be in the categories
GradedModulesWithBasis(A)only in the case of free modulesGradedModulesWithBasis(A.base_ring())for all modules, assuming we can determine a basis of each homogeneous piece, and this should be possible as long as the algebra has a distinguished basis.
Does that make sense?
This sounds like more of a question with the underlying mathematics that I can't answer.
Replying to @jhpalmieri:
Replying to @tscrim:
Replying to @dimpase:
maybe
sage.combinat.free_moduleought to be extended to accommodate for the needs of this ticket?+1 and we can likely use a lot of the stuff from the category, which means just implementing stuff at the parent level. It might be a bit slower than directly implementing it, but it might not be the bottleneck.
Although
CombinatorialFreeModuleis not exactly right for the modules here. At least in the free module case (which is as far as I've gotten), you only care about the degrees of the generators, you don't want to give them names, so there is no named basis. A typical element is listed as<a1, a2, ...>which means the sum ofa_i * generator_i, and this looks like a pretty efficient way to describe elements. We could create names, but they would be artificial.
I don't think there is anything wrong with having an artificial name for the basis elements. This is just implicit in Sage's R^n version of free modules, but we give a name to the basis all the time in math once we want to start working with a basis. However, using CFM is generally slower because its implementation is in Python, always sparse, and has some extra overhead because it allows more generic basis indices. Yet, you do gain the ability to handle infinite dimensional objects.
Note that
sage.modules.free_moduleis not suited for this, either: if you try to use it to create a free module over, say, the Steenrod algebra, you getUserWarning: You are constructing a free module over a noncommutative ring. Sage does not have a concept of left/right and both sided modules, so be careful. It's also not guaranteed that all multiplications are done from the right side.
Let S be the Steenrod algebra over a (commutative) ring R. Perhaps we should think of the free module as a representation of S over R, something you alluded to in your other comments. Internally, this seems to be how it is storing elements, as an infinite dimensional R-module
Replying to @jhpalmieri:
A more practical question: if we don't allow maps of nonzero degree in Hom, then how do we construct maps? Currently the easiest way to construct them is
Hom(M,N)(...values...), but that won't work if we changeHom.Homdoes take an extra argument,category, so we could use a different category to allow nonzero degree maps, although I'm not sure what that category should be called.
Strictly speaking, I think a map that shifts degree should not live in the category of graded modules. You are always fine using a larger category, such as the category of modules. However, we could potentially allow a slight abuse here and extend the correspondingHomset to take nonzero degree maps.
For now I am going to allow maps of nonzero degree, just because it makes it much easier to construct such maps.
I've created #32505 and I will push a branch there soon.
Comments on some changes made from here to #32505:
- Sage's other free module constructors take the ring/algebra as the first argument, so I've made the code here be consistent with that.
- I switched to use
CombinatorialFreeModulefor the modules,IndexedFreeModuleElementfor the elements. The finitely presented modules are not free over the corresponding algebras, but they are of course free over the base fields, and that's good enough for me. - As a result, the element classes no longer have
__init__methods.
Dependencies: #32505
Marking as "needs work" because we should deal with #32505 first, then build this on top of that.
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
72e455e | We do not require the base algebra's base ring to be a field. |
11b3725 | trac 32505: allow the resolution to be made up of maps between |
fcce24d | Merge branch 'public/modules/free_graded_modules-32505' of git://trac.sagemath.org/sage into public/modules/free_graded_modules-32505 |
2e0518f | Using free modules where possible and improved compatibility. |
6c1ab8d | trac 32505: more fixes |
6cf6d14 | Merge branch 'public/modules/free_graded_modules-32505' of git://trac.sagemath.org/sage into public/modules/free_graded_modules-32505 |
5074464 | Some last fixes and removing redundancy. |
ffe7179 | trac 32505: replace "PlusInfinity()" with "infinity" |
a1a9467 | trac 32505: remove redundant "zero" and "identity" methods |
4ed74b9 | trac 30680: rebased on top of 32505. |
Here is a branch so that we can start working on this, now that #32505 is positively reviewed. I did some clean-up on the old code, and it's almost all working, but not quite. I think that the problem is this: morphisms between finitely presented modules over the Steenrod algebra (the class of modules is currently called FPA_Module) is not quite behaving the way I want, and in particular, some of the time, domains and codomains of such morphisms are not in the class FPA_Module anymore. It is important that they be in this class because the code is using special properties of the Steenrod algebra to determine, for example, whether a morphism is injective: given two finitely presented modules, one can find a finite-dimensional subalgebra B such that a morphism as A-modules is injective if and only if it is injective as a B-module map. The case over the finite subalgebra is tractable.
But if we can't remember where the objects live, then we lose these special methods for A-modules, and so we get doctest failures. I'm seeing a few failures in module.py, I think all due to this.
By the way, I rewrote lots of profile.py and added a few doctests for odd primes, although we don't have any odd primary examples in the rest of the code. The new version of find_min_profile is about 10 times faster than the old version. When I get around to it, I will try some odd primary examples of modules and morphisms. Should I expect those to work?
The first two doctest failures:
sage -t --random-seed=52206228944996655655996976540735053542 src/sage/modules/fp_graded/steenrod/module.py
**********************************************************************
File "src/sage/modules/fp_graded/steenrod/module.py", line 484, in sage.modules.fp_graded.steenrod.module
Failed example:
h.is_injective() # Is ker(f) contained in K ?
Exception raised:
Traceback (most recent call last):
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 694, in _run
self.compile_and_execute(example, compiler, test.globs)
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 1088, in compile_and_execute
exec(compiled, globs)
File "<doctest sage.modules.fp_graded.steenrod.module[94]>", line 1, in <module>
h.is_injective() # Is ker(f) contained in K ?
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/modules/fp_graded/morphism.py", line 1634, in is_injective
j0 = self._resolve_kernel(top_dim, verbose)
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/modules/fp_graded/morphism.py", line 1752, in _resolve_kernel
raise ValueError('a top dimension must be specified for this calculation to terminate')
ValueError: a top dimension must be specified for this calculation to terminate
**********************************************************************
File "src/sage/modules/fp_graded/steenrod/module.py", line 540, in sage.modules.fp_graded.steenrod.module
Failed example:
res = Hko.resolution(6, verbose=True)
Exception raised:
Traceback (most recent call last):
File "sage/misc/cachefunc.pyx", line 1943, in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10347)
return cache[k]
KeyError: ((2,), ())
During handling of the above exception, another exception occurred:
Traceback (most recent call last):
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/modules/vector_space_homspace.py", line 395, in __call__
v = [C(a) for a in A]
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/modules/vector_space_homspace.py", line 395, in <listcomp>
v = [C(a) for a in A]
File "sage/structure/parent.pyx", line 898, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9388)
return mor._call_(x)
File "sage/structure/coerce_maps.pyx", line 161, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4665)
raise
File "sage/structure/coerce_maps.pyx", line 156, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4557)
return C._element_constructor(x)
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/modules/free_module.py", line 5769, in _element_constructor_
return FreeModule_generic_field._element_constructor_(self, e, *args, **kwds)
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/modules/free_module.py", line 1118, in _element_constructor_
return self.element_class(self, x, coerce, copy)
File "sage/modules/vector_mod2_dense.pyx", line 200, in sage.modules.vector_mod2_dense.Vector_mod2_dense.__init__ (build/cythonized/sage/modules/vector_mod2_dense.cpp:3952)
raise TypeError("x must be a list of the right length")
TypeError: x must be a list of the right length
During handling of the above exception, another exception occurred:
Traceback (most recent call last):
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 694, in _run
self.compile_and_execute(example, compiler, test.globs)
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/doctest/forker.py", line 1088, in compile_and_execute
exec(compiled, globs)
File "<doctest sage.modules.fp_graded.steenrod.module[105]>", line 1, in <module>
res = Hko.resolution(Integer(6), verbose=True)
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/modules/fp_graded/steenrod/module.py", line 1049, in resolution
res = FPModule.resolution(
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/modules/fp_graded/module.py", line 1269, in resolution
ret_complex.append(f._resolve_kernel(top_dim=top_dim,
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/modules/fp_graded/morphism.py", line 1768, in _resolve_kernel
self_n = self.vector_presentation(n)
File "sage/misc/cachefunc.pyx", line 1948, in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10483)
w = self._instance_call(*args, **kwds)
File "sage/misc/cachefunc.pyx", line 1824, in sage.misc.cachefunc.CachedMethodCaller._instance_call (build/cythonized/sage/misc/cachefunc.c:9949)
return self.f(self._instance, *args, **kwds)
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/modules/fp_graded/morphism.py", line 913, in vector_presentation
return Hom(D_n, C_n)([C_n.zero() if e.is_zero() else e.vector_presentation()
File "/Users/palmieri/Desktop/Sage/sage_builds/TESTING/sage-9.5/local/var/lib/sage/venv-python3.9/lib/python3.9/site-packages/sage/modules/vector_space_homspace.py", line 399, in __call__
raise ArithmeticError(msg)
ArithmeticError: some proposed image is not in the codomain, because
x must be a list of the right length
(There are others which fail because res is not defined after line 540 fails.)
The first failure is definitely because of the issue I mentioned above: the code should auto-detect an appropriate finite-dimensional algebra to work over, in which case we should not have to specify a top dimension, but clearly something is going wrong. I think that one of the morphisms is in the class FPMorphism rather than the Steenrod-specific FPA_Morphism. An example:
sage: from sage.modules.fp_graded.steenrod.module import FPA_Module
sage: A = SteenrodAlgebra()
sage: Hko = FPA_Module(A, [0], [[Sq(2)], [Sq(1)]])
sage: gen = Hko.generator(0)
sage: homspace = Hom(Hko, Hko)
sage: values = [Sq(0, 0, 1)*gen]
sage: f = homspace(values)
sage: # Good so far:
sage: type(f)
<class 'sage.modules.fp_graded.steenrod.homspace.FPA_ModuleHomspace_with_category_with_equality_by_id.element_class'>
sage: k = f.kernel_inclusion()
sage: type(k)
<class 'sage.modules.fp_graded.steenrod.homspace.FPA_ModuleHomspace_with_category_with_equality_by_id.element_class'>
sage: coker = k.cokernel_projection()
sage: type(coker)
<class 'sage.modules.fp_graded.steenrod.homspace.FPA_ModuleHomspace_with_category_with_equality_by_id.element_class'>
sage: # But this is a problem:
sage: type(coker.codomain())
<class 'sage.modules.fp_graded.module.FPModule_with_category'>
It should be FPA_Module_with_category. I don't know why this codomain is not in the right class.
I can fix the first problem by defining a method cokernel_projection for FPA_Morphism, just reproducing the code for FPMorphism. I don't know if there is a better solution. I'm now working on the other doctest failure.
Branch pushed to git repo; I updated commit sha1. New commits:
a9741cb | trac 30680: bug fixes |
Okay, I found a bug and fixed it, and that took care of most of the problems. Something like the first issue I mentioned is still occurring: I don't know how to naturally force a morphism to be in the right class. The remaining failure comes from this doctest:
sage: def is_exact(res):
....: for i in range(len(res)-1):
....: h = res[i].homology(res[i+1])
....: if not h.codomain().is_trivial():
....: return False
....: return True
sage: is_exact(res)
True
The problem is that the maps in res are maps of FreeGradedModules, so they are not in the Steenrod-specific world, so the homology computation doesn't work.
In case you're interested, the bug is a subtle one in the code from #32505: to compute the coefficients of an element in a free module, we were using
return self.dense_coefficient_list()
but the default ordering for the coefficients is in increasing order of degree, not the specified order for the generators. We were hitting a situation in which this mattered, and changing to this fixed it:
order = self.parent()._indices
return self.dense_coefficient_list(order)
I will add some doctests that capture this.
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
67e78ed | trac 30680: bug fixes |
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
fb130d2 | trac 30680: bug fixes |
We should now be at 100% coverage and one doctest failure. I'm sure there are typos and plenty of room for other improvements, but just about everything is now working. I still haven't tried odd primes.
One quick thought is to add an attribute or someway to let the morphism code know what type of modules to create. It might work by using type(self.codomain()) or similar (with perhaps some care to make sure it is not the category-mangled object). This would avoid a lot of code and documentation duplication with making it more future-proof.
I am quite surprised by this bug and slightly worried because it should not matter about the order (as long as internally each class knows how to go back and forth between consistently).
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
bf9fcdb | trac 30680: bug fixes |
I wonder if there is some simple modification to the code for resolution for Steenrod algebra modules:
def resolution(self, k, top_dim=None, verbose=False):
"""
(documentation omitted)
"""
algebra = self.base_ring()
finite_algebra = SteenrodAlgebra_generic(algebra.prime(), profile=self.profile())
# Change rings to the finite algebra, and call the base class
# implementation of this function.
res = FPModule.resolution(
self.change_ring(finite_algebra),
k,
top_dim=top_dim,
verbose=verbose)
# Change rings back to the original Steenrod algebra.
return [j.change_ring(self.base_ring()) for j in res]Something at the end that does more than just change the ring, but also forces the morphism to have the right class. This code explicitly calls FPModule.resolution, and that's probably the root of the problem. We could completely duplicate the general resolution code to the Steenrod algebra setting, but there must be a better way.
By the way, although A is a standard thing for homotopy theorists to call the Steenrod algebra, FPA_Module is not the most evocative name, I think. SteenrodModule? SteenrodFPModule? What should we call the class? (Have to get a jump on the bike-shedding.)
Replying to @jhpalmieri:
I wonder if there is some simple modification to the code for
resolutionfor Steenrod algebra modules:
Something at the end that does more than just change the ring, but also forces the morphism to have the right class. This code explicitly calls
FPModule.resolution, and that's probably the root of the problem.
We could, for example, change each map by reconstructing each domain and codomain, using FPA_Module to instantiate them, and then reconstructing each morphism. It should be easy to write a method or a private function that does this.
Replying to @tscrim:
I am quite surprised by this bug and slightly worried because it should not matter about the order (as long as internally each class knows how to go back and forth between consistently).
Indeed, my "fix" has broken something. This works:
sage: from sage.modules.fp_graded.free_module import FreeGradedModule
sage: F.<x,y> = FreeGradedModule(A, (2, 0))
sage: x.degree()
2
sage: y.degree()
0
This doesn't:
sage: from sage.modules.fp_graded.module import FPModule
sage: A = SteenrodAlgebra()
sage: M.<x,y> = FPModule(A, (2, 0))
sage: x.degree()
0
sage: y.degree()
2
To compute the degree of an element of an FPModule, it first computes a lift to a free module and then computes the degree there, but when computing that lift, it mixes up the order of the generators.
sage: x.lift_to_free()
y
This is somehow due to imposing the order in coefficients.
This fixes some of these problems, although I think I still need to specify the order in dense_coefficient_list:
diff --git a/src/sage/modules/fp_graded/element.py b/src/sage/modules/fp_graded/element.py
index 87f52b759a..51d48f405e 100755
--- a/src/sage/modules/fp_graded/element.py
+++ b/src/sage/modules/fp_graded/element.py
@@ -122,7 +122,7 @@ class FPElement(IndexedFreeModuleElement):
sage: y.coefficients()
[0, Sq(2)]
"""
- return [self[i] for i in sorted(self.parent().indices())]
+ return [self[i] for i in self.parent().indices()]
def _lmul_(self, a):Let's work on the bugs in finitely presented modules in #33275 (I hope quickly) and then deal with the issues specific to the Steenrod algebra here.
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ba19b0b | trac 30680: rebased on top of #33275 |
Branch pushed to git repo; I updated commit sha1. New commits:
47b3ce8 | trac 30680: use dense_coefficient_list |
I don't know for your other questions off the top of my head (I am out the door to go back home now), but I am a big +1 for renaming to something like SteenrodFPModule. I will think about the other questions and reply tomorrow.
Branch pushed to git repo; I updated commit sha1. New commits:
a2dc039 | trac 30680: use "SteenrodFPModule" etc for class names |
Thank you.
Okay, so I have two ways out of this issue of not having the correct class specified when building, e.g., the resolution:
- We introduce a method, say,
_graded_module_class()(that takes a parameterfree) that returns the corresponding class. - We use
type(self.codomain())and attach, via an attribute, the free module class to each FP module.
I am maybe slightly preferential towards 2 since it is local to the module implementation (which is what needs this information) rather than more global to the algebras. We might have some consistency issues to address (such as the free modules not taking a morphism as defining information), but these will likely improve the overall quality and robustness of the code.
To make sure we're on the same page, there are (I think) two problems with resolution: (a) if M is an instance of SteenrodFPModule, then M.resolution(...) forgets that and returns morphisms that come from FPModule (or FreeGradedModule) rather than SteenrodFPModule. Then (b) if I fix that by converting all of the morphism back to SteenrodFPModuleMorphism, the resulting objects are not recognized as free, so for example they will be described in the string representation as being "finitely presented."
I think that since we used FreeGradedModule more than was originally planned by the authors in #32505, we may now need SteenrodFreeModule and similar classes for morphisms and homspaces.
Here is what I'm currently using to convert the maps:
diff --git a/src/sage/modules/fp_graded/steenrod/module.py b/src/sage/modules/fp_graded/steenrod/module.py
index c74ed1535ca..9a19a87f65f 100755
--- a/src/sage/modules/fp_graded/steenrod/module.py
+++ b/src/sage/modules/fp_graded/steenrod/module.py
@@ -827,6 +827,7 @@ AUTHORS:
# https://www.gnu.org/licenses/
# ****************************************************************************
+from sage.categories.homset import Hom
from sage.rings.infinity import infinity
from sage.algebras.steenrod.steenrod_algebra import SteenrodAlgebra_generic
from sage.modules.fp_graded.module import FPModule
@@ -1056,7 +1057,7 @@ class SteenrodFPModule(FPModule):
verbose=verbose)
# Change rings back to the original Steenrod algebra.
- return [j.change_ring(self.base_ring()) for j in res]
+ return [convert_map(j.change_ring(self.base_ring())) for j in res]
def export_module_definition(self, powers_of_two_only=True):
@@ -1181,3 +1182,21 @@ class SteenrodFPModule(FPModule):
len(values),
" ".join(["%d" % x for x in values])))
element_index += 1
+
+
+def convert_map(f):
+ if f.domain().has_relations():
+ D = SteenrodFPModule(f.domain()._j)
+ else:
+ try:
+ D = SteenrodFPModule(f.domain()._free_module())
+ except AttributeError:
+ D = SteenrodFPModule(f.domain().base_ring(), f.domain()._generator_degrees)
+ if f.codomain().has_relations():
+ C = SteenrodFPModule(f.codomain()._j)
+ else:
+ try:
+ C = SteenrodFPModule(f.codomain()._free_module())
+ except AttributeError:
+ C = SteenrodFPModule(f.codomain().base_ring(), f.codomain()._generator_degrees)
+ return Hom(D, C)(f.values())