Finitely presented modules over the Steenrod algebra

[catanzaromj]

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

[catanzaromj]

Branch: u/gh-catanzaromj/finitely_presented_modules_over_the_steenrod_algebra

[catanzaromj]

Author: Bob Bruner, Michael Catanzaro, Sverre Lunøe-Nielsen, Koen van Woerden

[catanzaromj]

Changed branch from u/gh-catanzaromj/finitely_presented_modules_over_the_steenrod_algebra to none

[catanzaromj]

Changed keywords from none to Steenrod algebra, modules, homological algebra

[catanzaromj]

Commit: cc69ed5

[catanzaromj]

Branch: u/gh-catanzaromj/finitely_presented_modules_over_the_steenrod_algebra

[sagetrac-git]

Changed commit from cc69ed5 to 81fb0c1

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

81fb0c1

Replace `_cmp_` with _richcmp_

[sagetrac-git]

Changed commit from 81fb0c1 to 190da7f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e78ca19	Replace overset with xrightarrow and remove unused imports
190da7f	Remove additional unused imports

[tscrim]

comment:8

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:

1. Could this be split up into smaller tickets? This would make the review much easier.
2. I think you could rename finitely_presented_over_the_steenrod_algebra to fp_over_steenrod_algebra in order to make the file paths shorter to type.
3. 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.
4. Use the Sage default latex commands of \ZZ, \GF{p}, etc. so the documentation is standardized.
5. 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::).
6. 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 a RuntimeError unless you have a very good reason to; NotImplementedError, TypeError, and ValueError are usually much better.
7. 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 does TestSuite(foo).run(). This is also a common pattern in Sage.

[sverre320]

comment:9

tscrim,

Thanks for the quick follow-up. Here are some preliminary answers:

1. 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.

2. 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.

[tscrim]

comment:10

1. 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.

2. 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.

[sagetrac-git]

Changed commit from 190da7f to de83eea

[sagetrac-git]

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

[sverre320]

Performance of the original Python code.

[sverre320]

Attachment: python_perf_res.csv.gz

Performance of the cythonized code.

[sverre320]

Attachment: cython_perf_res.csv.gz

Attachment: perf.png

visualization of the performance data combined

[sverre320]

visualization of total time (green colors) and accounted time (red colors) for both python and cythonized code.

[sverre320]

Attachment: perf_accounted_time.png

Visualization of performance data where only time spent in external modules are shown

[sverre320]

Attachment: perf_comp.png

Attachment: perf_cython.png

Visualization of performance data for cython code only.

[dimpase]

comment:145

Can we now do e.g. FPModules over finitely presented group algebras?

[jhpalmieri]

comment:146

Well, the basic setup in #32505 is for f.p. modules specifically over graded rings, and in parts of the code you want to compute the basis for a particular homogeneous piece, so this relies on the graded ring and the graded module being finite enough that each homogeneous piece is finite-dimensional. It's certainly worth exploring how much the code can be pushed when the graded ring is concentrated in degree zero and is infinite dimensional, but I don't know if anything would work with the current state of things.

[jhpalmieri]

comment:147

One of the nice observations about the Steenrod algebra is that it is a union of finite-dimensional subalgebras, and you can do many useful calculations by restricting to those subalgebras. So maybe everything should in principle work if you have something like an algebra which is filtered by finite-dimensional subalgebras (and if you want to do homological algebra, you probably want each algebra filtration piece to be free over its subalgebra filtration pieces). Some motivated person should look into this.

[vbraun]

comment:148

Documentation doesn't build

[tscrim]

Changed commit from 7edf174 to 9bde37e

[tscrim]

Changed branch from u/jhpalmieri/fp_modules_steenrod-30680 to u/tscrim/fp_modules_steenrod-30680

[tscrim]

comment:149

Without this change, I see the same error as reported by the patchbot. I figured my linking to the index.rst was harmless, but it exposed something that wasn't done properly.

---

New commits:

43c1bfc	Merge branch 'u/jhpalmieri/fp_modules_steenrod-30680' of git://trac.sagemath.org/sage into u/tscrim/fp_modules_steenrod-30680
9bde37e	Small tweak to the doc.

[jhpalmieri]

Changed branch from u/tscrim/fp_modules_steenrod-30680 to u/jhpalmieri/fp_modules_steenrod-30680

[jhpalmieri]

Changed commit from 9bde37e to 6821e04

[jhpalmieri]

comment:151

I was independently trying basically the same thing. I've added one line.

---

New commits:

c144912	Merge branch 'develop' into t/30680/fp_modules_steenrod-30680
1b0de4f	Merge branch 'u/tscrim/fp_modules_steenrod-30680' of trac.sagemath.org:sage into t/30680/fp_modules_steenrod-30680
6821e04	trac 30680: add utf-8 coding info

[jhpalmieri]

comment:152

PDF documentation doesn't build. I'm looking into it.

[sagetrac-git]

Changed commit from 6821e04 to 7035ae5

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3d427b5	Merge branch 'develop' into t/30680/fp_modules_steenrod-30680
b671378	Merge branch 'u/jhpalmieri/fp_modules_steenrod-30680' of trac.sagemath.org:sage into t/30680/fp_modules_steenrod-30680
7035ae5	trac 30680: use "nowrap" directive before LaTeX align environment

[jhpalmieri]

comment:154

Fixed. It's an issue mentioned in our documentation about the :nowrap: directive.

[tscrim]

comment:155

Thank you for the catch and fix. I probably would have used aligned instead, but this fix is good too. :)

[vbraun]

Changed branch from u/jhpalmieri/fp_modules_steenrod-30680 to 7035ae5