Opened 5 years ago

Closed 4 years ago

Last modified 3 months ago

#18066 closed enhancement (fixed)

Cleanup of ModulesWithBasis and friends

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-6.10
Component: categories Keywords:
Cc: nthiery, darij, aschilling, zabrocki, jhpalmieri Merged in:
Authors: Travis Scrimshaw Reviewers: Darij Grinberg
Report Upstream: N/A Work issues:
Branch: 96004df (Commits) Commit:
Dependencies: Stopgaps:

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.

Change History (27)

comment:1 Changed 4 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:

f8bd451Moving code up from CFM to modules_with_basis.

comment:2 follow-up: Changed 4 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: Changed 4 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 4 years ago by darij (previous) (diff)

comment:4 Changed 4 years ago by git

  • Commit changed from f8bd45183a2894e9260073209ecd8b93b957f6c4 to aa444d2681187c178d9eca7c410468056a14bb3d

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

aa444d2Fixing doctests, trying to improve compatibility, and some changes.

comment:5 Changed 4 years ago by git

  • Commit changed from aa444d2681187c178d9eca7c410468056a14bb3d to 954e3542ccc00ef3cc294f19019da3608d87a5a8

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

954e354Added a test Darij requested.

comment:6 in reply to: ↑ 3 Changed 4 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.

Replying to darij:

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)?

Added.

comment:7 in reply to: ↑ 3 ; follow-up: Changed 4 years ago by nthiery

Replying to 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.

comment:8 in reply to: ↑ 2 ; follow-up: Changed 4 years ago by nthiery

Replying to 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.

comment:9 Changed 4 years ago by nthiery

Thanks for the progress on that btw!

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

Replying to nthiery:

Replying to 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 4 years ago by darij

Replying to nthiery:

Replying to 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 4 years ago by git

  • Commit changed from 954e3542ccc00ef3cc294f19019da3608d87a5a8 to 2a935f54705b998469f68f54cc8af77c440fb1f7

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

2a935f5Made FreeModules in the category of finite dimensional free modules with basis.

comment:13 Changed 4 years ago by git

  • Commit changed from 2a935f54705b998469f68f54cc8af77c440fb1f7 to 7c0223af13ccb7e92191eea50431b3ebc477dbc7

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

570bc49Merge branch 'public/categories/super_categories-18044' into 6.9.b1
b91cd82trac #18044 correct one typo in the doc
7fd1df2Merge branch 'public/categories/super_categories-18044' of trac.sagemath.org:sage into public/categories/super_categories-18044
0579337Some reviewer tweaks and doc additions.
aec22ccAdded one more test.
4b2046fMerge branch 'public/categories/super_categories-18044' into public/categories/filtered_algebras-17096
3f67b6bFixing trivial doctest due to changes in category heirarchy.
fa476ddFixing double-colon in INPUT block.
6cc8b84Reviewer changes with Darij.
7c0223aMerge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/categories/cleanup_CFM_modules_wBasis-18066

comment:14 Changed 4 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 4 years ago by tscrim (previous) (diff)

comment:15 Changed 4 years ago by git

  • Commit changed from 7c0223af13ccb7e92191eea50431b3ebc477dbc7 to c504110a3d44de5381b3ed33ed5d9765e2b060a9

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

caa5323Merge branch 'develop' into public/categories/cleanup_CFM_modules_wBasis-18066
c504110Merge branch 'develop' into public/categories/cleanup_CFM_modules_wBasis-18066

comment:16 Changed 4 years ago by git

  • Commit changed from c504110a3d44de5381b3ed33ed5d9765e2b060a9 to 913a0c14f45142e5f80579c58147174daa18f27b

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

913a0c1Fixing doctest/tab issues from merge.

comment:17 Changed 4 years ago by git

  • Commit changed from 913a0c14f45142e5f80579c58147174daa18f27b to b32e479bffac439f3cfb561027dfebc871d01528

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

07cc00118411: Fixed unused import
7c103df18411: cleanup spacing for optional arguments
a35ef8a18411: proofreading
22f8b7718411: proofreading
4a9fd81Trac 18411: merge Sage 6.10.beta0
525d038Trac 18411: Fix doctest in colored_permutations.py
41af762Trac 18411: pass keywords in __call__
6e27ddeTrac 18411: merge sage-6.10.beta1
b21396cMerge branch '18411' into HEAD
b32e479further changes (mostly doc)

comment:18 Changed 4 years ago by git

  • Commit changed from b32e479bffac439f3cfb561027dfebc871d01528 to e2fb14a393beb5e40519df8cf7ae06b077a398b0

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

dbb5789Further fixes
e2fb14aremove _test_keytype since submodules of free modules are currently failing it

comment:19 Changed 4 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 4 years ago by tscrim

  • Status changed from needs_review to positive_review

comment:21 Changed 4 years ago by tscrim

  • Reviewers set to Darij Grinberg

comment:22 Changed 4 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 item had failures:
   1 of   5 in sage.geometry.linear_expression.LinearExpression.monomial_coefficients
    [165 tests, 1 failure, 1.47 s]

comment:23 Changed 4 years ago by git

  • Commit changed from e2fb14a393beb5e40519df8cf7ae06b077a398b0 to 96004dfa8a3368fe4f2fe122268744d9f6e4bf79

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

96004dfDarij...

comment:24 Changed 4 years ago by tscrim

  • Status changed from needs_work to positive_review

comment:25 Changed 4 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 4 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 3 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.