Opened 6 years ago

Closed 5 years ago

# Cleanup of ModulesWithBasis and friends

Reported by: Owned by: tscrim tscrim major sage-6.10 categories nthiery, darij, aschilling, zabrocki, jhpalmieri Travis Scrimshaw Darij Grinberg N/A 96004df (Commits)

### Description

Currently ModulesWithBasis requires its implementations to behave like CombinatorialFreeModule, along with having an indexing set for the basis which is comparable. The aim of this ticket is to move various methods from CombintorialFreeModule and it's element class to ModulesWithBasis. This ticket will also give better generic functionality, such as a default implementation of support.

### comment:1 Changed 5 years ago by tscrim

• Authors set to Travis Scrimshaw
• Branch set to public/categories/cleanup_CFM_modules_wBasis-18066
• Commit set to f8bd45183a2894e9260073209ecd8b93b957f6c4
• Milestone changed from sage-6.6 to sage-6.10
• Status changed from new to needs_review

Okay, I figured this was the best starting point for trying to see if the quack of a free module echoes. For this ticket, I moved many methods up and was able to generalize them. There were only minimal changes needed to remove the ordering on support (only the Macdonald basis of Sym) and make monomial_coefficients() an abstract method. I added the copy parameter to monomial coefficients for both speed and dict in the usual free modules has this API. Most of the other changes are trivial changes to doctest output.

The next thing to do would be to check to see if #10672 becomes invalid because of this ticket (execpt perhaps the iteration issue). After that, then move onto either merging CFM and (sparse?) free modules #10671 or rebasing and finalizing #18310.

New commits:

 ​f8bd451 Moving code up from CFM to modules_with_basis.

### comment:2 follow-up: ↓ 8 Changed 5 years ago by tscrim

Also a question mostly for Nicolas, do we still need _apply_module_morphism? Is it just a method so that we don't have to create a full morphism object?

### comment:3 follow-ups: ↓ 6 ↓ 7 Changed 5 years ago by darij

+1! This is the way to go, and thanks for doing it.

However, one thing I'm still missing is an explicit explanation of what methods one needs to implement in order to inherit from ModulesWithBasis. I suspect this is no longer up-to-date:

        # To implement a module_with_basis you need to implement either
#   basis() or an _indices attribute and monomial().


(as in, we probably need more now), right?

Coercion of coefficients into the base ring needs to be carefully thought over. As of now, I am not sure if it works correctly. For instance, term does no coercion, but __invert__ does self.parent().term(one, ~mcs[one]), although the inversion operator ~ might produce an element of a bigger ring (for example, ~(ZZ(2)) returns 1/2).

One more thing, which is probably not your fault but just caught my eyes. The docstring of module_morphism says:

            - matrix   -- a matrix of size \dim X \times \dim Y
or \dim Y \times \dim X


I don't see why the "or" is here. The doctests show that \dim Y \times \dim X works, but does \dim X \times \dim Y work too? And if so, *should* it? I think checking whether the matrix has the "wrong" dimensions, and then trying to fix them by transposing it, would be a brittle paradigm.

Also, could we have doctests proving that the monomial_coefficients method works correctly (including not mutating the dictionary unless explicitly required) on various instances of ModulesWithBasis (e.g., vector spaces)? Thank you!

Last edited 5 years ago by darij (previous) (diff)

### comment:4 Changed 5 years ago by git

• Commit changed from f8bd45183a2894e9260073209ecd8b93b957f6c4 to aa444d2681187c178d9eca7c410468056a14bb3d

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

 ​aa444d2 Fixing doctests, trying to improve compatibility, and some changes.

### comment:5 Changed 5 years ago by git

• Commit changed from aa444d2681187c178d9eca7c410468056a14bb3d to 954e3542ccc00ef3cc294f19019da3608d87a5a8

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

 ​954e354 Added a test Darij requested.

### comment:6 in reply to: ↑ 3 Changed 5 years ago by tscrim

• Cc aschilling zabrocki jhpalmieri added

So in my latest commit I fixed doctests. Some were trivial due to support no longer being ordered (and hence changes to the k-schur book tests and the cc of Anne and Mike), some were more substantial:

• ChainComplexes when passed a field said VectorSpaces, and so it did not consider itself as having a distinguished basis. However, if you give it a ring (like ZZ), then it became in ModulesWithBasis (=FreeModules), which it currently does not live from what I saw. Since there wasn't anything using this extra functionality (any attempt to use it was likely broken), I opted to downgrade the category to just Modules. (John, I cc'ed you to let you know.)
• I added a dense_coefficient_list for finite dimensional modules with basis so that you could get an ordered list of coefficients including 0's. This was needed for hyperplane arrangements. I'm open to different names.
• I made the linear expression code be in finite dimensional modules with basis.

However, one thing I'm still missing is an explicit explanation of what methods one needs to implement in order to inherit from ModulesWithBasis. I suspect this is no longer up-to-date:

        # To implement a module_with_basis you need to implement either
#   basis() or an _indices attribute and monomial().


(as in, we probably need more now), right?

I put that in there because that is all that should be required. However, how the code breaks and the traceback tells you everything you need to know as far as what to implement.

Coercion of coefficients into the base ring needs to be carefully thought over. As of now, I am not sure if it works correctly. For instance, term does no coercion, but __invert__ does self.parent().term(one, ~mcs[one]), although the inversion operator ~ might produce an element of a bigger ring (for example, ~(ZZ(2)) returns 1/2).

Actually my generic implementation should handle this with grace as it is coeff * self.monomial(index). However, CFM currently does not do any coercion as indicated in the docstring, but that is a discussion for another ticket.

One more thing, which is probably not your fault but just caught my eyes. The docstring of module_morphism says:

            - matrix   -- a matrix of size \dim X \times \dim Y
or \dim Y \times \dim X


I don't see why the "or" is here. The doctests show that \dim Y \times \dim X works, but does \dim X \times \dim Y work too? And if so, *should* it? I think checking whether the matrix has the "wrong" dimensions, and then trying to fix them by transposing it, would be a brittle paradigm.

I don't know and I don't really care as that is outside of the scope of this ticket.

Also, could we have doctests proving that the monomial_coefficients method works correctly (including not mutating the dictionary unless explicitly required) on various instances of ModulesWithBasis (e.g., vector spaces)?

### comment:7 in reply to: ↑ 3 ; follow-up: ↓ 11 Changed 5 years ago by nthiery

One more thing, which is probably not your fault but just caught my eyes. The docstring of module_morphism says:

            - matrix   -- a matrix of size \dim X \times \dim Y
or \dim Y \times \dim X


I don't see why the "or" is here. The doctests show that \dim Y \times \dim X works, but does \dim X \times \dim Y work too? And if so, *should* it? I think checking whether the matrix has the "wrong" dimensions, and then trying to fix them by transposing it, would be a brittle paradigm.

Which of the two it is depends on the value of the optional side argument. No worry, there is no attempt at "fixing" things by transposition.

### comment:8 in reply to: ↑ 2 ; follow-up: ↓ 10 Changed 5 years ago by nthiery

Also a question mostly for Nicolas, do we still need _apply_module_morphism? Is it just a method so that we don't have to create a full morphism object?

As far as I know, that was indeed the motivation when Mike H implemented it. I imagine it can make sense in certain cases where many different morphisms are applied. But I don't have a strong opinion either.

### comment:9 Changed 5 years ago by nthiery

Thanks for the progress on that btw!

### comment:10 in reply to: ↑ 8 Changed 5 years ago by tscrim

Also a question mostly for Nicolas, do we still need _apply_module_morphism? Is it just a method so that we don't have to create a full morphism object?

As far as I know, that was indeed the motivation when Mike H implemented it. I imagine it can make sense in certain cases where many different morphisms are applied. But I don't have a strong opinion either.

I ended up doing something for diagram algebras where I found this to be useful (although I could have used a full morphism to work around it), so I'm happy enough to keep it around for now.

### comment:11 in reply to: ↑ 7 Changed 5 years ago by darij

One more thing, which is probably not your fault but just caught my eyes. The docstring of module_morphism says:

            - matrix   -- a matrix of size \dim X \times \dim Y
or \dim Y \times \dim X


I don't see why the "or" is here. The doctests show that \dim Y \times \dim X works, but does \dim X \times \dim Y work too? And if so, *should* it? I think checking whether the matrix has the "wrong" dimensions, and then trying to fix them by transposing it, would be a brittle paradigm.

Which of the two it is depends on the value of the optional side argument. No worry, there is no attempt at "fixing" things by transposition.

Ah, thank you! I didn't see this, as the argument is hidden inside the **keywords.

### comment:12 Changed 5 years ago by git

• Commit changed from 954e3542ccc00ef3cc294f19019da3608d87a5a8 to 2a935f54705b998469f68f54cc8af77c440fb1f7

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

 ​2a935f5 Made FreeModules in the category of finite dimensional free modules with basis.

### comment:13 Changed 5 years ago by git

• Commit changed from 2a935f54705b998469f68f54cc8af77c440fb1f7 to 7c0223af13ccb7e92191eea50431b3ebc477dbc7

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

 ​570bc49 Merge branch 'public/categories/super_categories-18044' into 6.9.b1 ​b91cd82 trac #18044 correct one typo in the doc ​7fd1df2 Merge branch 'public/categories/super_categories-18044' of trac.sagemath.org:sage into public/categories/super_categories-18044 ​0579337 Some reviewer tweaks and doc additions. ​aec22cc Added one more test. ​4b2046f Merge branch 'public/categories/super_categories-18044' into public/categories/filtered_algebras-17096 ​3f67b6b Fixing trivial doctest due to changes in category heirarchy. ​fa476dd Fixing double-colon in INPUT block. ​6cc8b84 Reviewer changes with Darij. ​7c0223a Merge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/categories/cleanup_CFM_modules_wBasis-18066

### comment:14 Changed 5 years ago by tscrim

It wasn't letting me post this comment:

To fix the failing doctests, I made the free modules be in the category of finite dimensional modules with basis, which I believe they should have been awhile ago. I also merged in the filtered algebras patch.

Last edited 5 years ago by tscrim (previous) (diff)

### comment:15 Changed 5 years ago by git

• Commit changed from 7c0223af13ccb7e92191eea50431b3ebc477dbc7 to c504110a3d44de5381b3ed33ed5d9765e2b060a9

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

 ​caa5323 Merge branch 'develop' into public/categories/cleanup_CFM_modules_wBasis-18066 ​c504110 Merge branch 'develop' into public/categories/cleanup_CFM_modules_wBasis-18066

### comment:16 Changed 5 years ago by git

• Commit changed from c504110a3d44de5381b3ed33ed5d9765e2b060a9 to 913a0c14f45142e5f80579c58147174daa18f27b

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

 ​913a0c1 Fixing doctest/tab issues from merge.

### comment:17 Changed 5 years ago by git

• Commit changed from 913a0c14f45142e5f80579c58147174daa18f27b to b32e479bffac439f3cfb561027dfebc871d01528

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

 ​07cc001 18411: Fixed unused import ​7c103df 18411: cleanup spacing for optional arguments ​a35ef8a 18411: proofreading ​22f8b77 18411: proofreading ​4a9fd81 Trac 18411: merge Sage 6.10.beta0 ​525d038 Trac 18411: Fix doctest in colored_permutations.py ​41af762 Trac 18411: pass keywords in __call__ ​6e27dde Trac 18411: merge sage-6.10.beta1 ​b21396c Merge branch '18411' into HEAD ​b32e479 further changes (mostly doc)

### comment:18 Changed 5 years ago by git

• Commit changed from b32e479bffac439f3cfb561027dfebc871d01528 to e2fb14a393beb5e40519df8cf7ae06b077a398b0

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

 ​dbb5789 Further fixes ​e2fb14a remove _test_keytype since submodules of free modules are currently failing it

### comment:19 Changed 5 years ago by darij

Great job, Travis. If you are fine with my edits and the doctests agree, this is a positive_review.

I am somewhat unhappy about the fact that submodules of free modules don't play nicely with monomial_coefficients (if M is a submodule of R^n given as the span of some vectors, then m.monomial_coefficients for m \in M gives me the monomial coefficients of m with respect to the standard basis of R^n, not with respect to any basis of M), but this is hardly a flaw of this particular ticket.

### comment:20 Changed 5 years ago by tscrim

• Status changed from needs_review to positive_review

### comment:21 Changed 5 years ago by tscrim

• Reviewers set to Darij Grinberg

### comment:22 Changed 5 years ago by vbraun

• Status changed from positive_review to needs_work

How about running the tests before setting something to positive review?

sage -t --long src/sage/geometry/linear_expression.py
**********************************************************************
File "src/sage/geometry/linear_expression.py", line 183, in sage.geometry.linear_expression.LinearExpression.monomial_coefficients
Failed example:
sorted(linear.monomial_coefficients().items()
Exception raised:
Traceback (most recent call last):
File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
self.compile_and_execute(example, compiler, test.globs)
File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 856, in compile_and_execute
compiled = compiler(example)
File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 494, in <lambda>
example.source, filename, "single", compileflags, 1)
File "<doctest sage.geometry.linear_expression.LinearExpression.monomial_coefficients[3]>", line 1
sorted(linear.monomial_coefficients().items()
^
SyntaxError: unexpected EOF while parsing
**********************************************************************
1 of   5 in sage.geometry.linear_expression.LinearExpression.monomial_coefficients
[165 tests, 1 failure, 1.47 s]


### comment:23 Changed 5 years ago by git

• Commit changed from e2fb14a393beb5e40519df8cf7ae06b077a398b0 to 96004dfa8a3368fe4f2fe122268744d9f6e4bf79

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

 ​96004df Darij...

### comment:24 Changed 5 years ago by tscrim

• Status changed from needs_work to positive_review

### comment:25 Changed 5 years ago by darij

Thanks Travis! (I've just fired up my virtual machine a few minutes ago to deal with this...)

Note to self: do test sage/geometry...

### comment:26 Changed 5 years ago by vbraun

• Branch changed from public/categories/cleanup_CFM_modules_wBasis-18066 to 96004dfa8a3368fe4f2fe122268744d9f6e4bf79
• Resolution set to fixed
• Status changed from positive_review to closed

### comment:27 Changed 18 months ago by dimpase

• Commit 96004dfa8a3368fe4f2fe122268744d9f6e4bf79 deleted

in src/sage/categories/modules_with_basis.py one still sees

   Once :trac:18066 is merged


namely here:

9bc28fd5fdb (Travis Scrimshaw  2015-03-26 23:33:19 -0700  129)         This category currently requires an implementation of an
6cc8b8460df (Travis Scrimshaw  2015-10-04 16:20:51 -0500  130)         element method support. Once :trac:18066 is merged, an
6cc8b8460df (Travis Scrimshaw  2015-10-04 16:20:51 -0500  131)         implementation of an items method will be required.

Note: See TracTickets for help on using tickets.