Opened 8 years ago

Closed 7 years ago

#17096 closed enhancement (fixed)

Implement categories for filtered algebras

Reported by: tscrim Owned by: tscrim
Priority: major Milestone: sage-6.10
Component: categories Keywords: filtered algebras
Cc: nthiery, darij, days64, sd67 Merged in:
Authors: Travis Scrimshaw Reviewers: Darij Grinberg
Report Upstream: N/A Work issues:
Branch: 6cc8b84 (Commits, GitHub, GitLab) Commit: 6cc8b8460dfe5a05380e73e667dc7294e4369774
Dependencies: #18044 Stopgaps:

Status badges

Description

There are some upcoming algebras in Sage (Clifford algebras in #15300, Yangians in #15484, and orthogonal/symplectic basis for Sym #15536; likely others) that would benefit from having a category with common methods.

Change History (99)

comment:1 follow-up: Changed 8 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Branch set to public/categoires/filtered_algebras-17096
  • Commit set to ad184efacc9ceabfb1179ccd4d677786f4713b01
  • Status changed from new to needs_review

Some design decisions:

  • Every graded algebra is a filtered algebra under the "natural" filtration of summing over (weakly) smaller degrees (assuming total ordering on the grading group). This is implicit in the category structure; nothing specific is implemented.
  • Every graded_* category has filtered_* as an immediate super category. In particular, this is needed for GradedAlgebrasWithBasis not picking up FilteredAlgebrasWithBasis in its super categories otherwise.
  • Homogeneous elements for filtered algebras are elements in Fi not in Fi-1. I don't know if this is a standard definition, but it allowed extensions of methods from graded to filtered.

Needs review.


New commits:

ad184efImplemented filtered modules/algebras and associated graded algebras.

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

Replying to tscrim:

  • Every graded algebra is a filtered algebra under the "natural" filtration of summing over (weakly) smaller degrees (assuming total ordering on the grading group). This is implicit in the category structure; nothing specific is implemented.

Of course, depending on the context, the converse convention can also sense; but maybe that's ok because eventually we will have both filtered and descendingFiltered (or something similar) categories.

http://en.wikipedia.org/wiki/Filtration_%28mathematics%29

  • Every graded_* category has filtered_* as an immediate super category. In particular, this is needed for GradedAlgebrasWithBasis not picking up FilteredAlgebrasWithBasis in its super categories otherwise.

This seems like the same situation as for quotients w.r.t. subquotients. So the same mechanism should do the job (see sage.categories.quotients.Quotients.default_super_categories). Please confirm!

  • Homogeneous elements for filtered algebras are elements in Fi not in Fi-1. I don't know if this is a standard definition, but it allowed extensions of methods from graded to filtered.

I see the point. The inconvenient is of course that this makes the set of homogeneous elements for a given i not be a vector space. What do you do with 0 btw?

Cheers,

Nicolas

comment:3 in reply to: ↑ 2 Changed 8 years ago by tscrim

  • Branch changed from public/categoires/filtered_algebras-17096 to public/categories/filtered_algebras-17096
  • Commit changed from ad184efacc9ceabfb1179ccd4d677786f4713b01 to bb234ec71d1276c6cc14320074b3de6fdc606192

Replying to nthiery:

Of course, depending on the context, the converse convention can also sense; but maybe that's ok because eventually we will have both filtered and descendingFiltered (or something similar) categories.

http://en.wikipedia.org/wiki/Filtration_%28mathematics%29

True, but I figured we'd cross that bridge when we have a need/desire for it.

This seems like the same situation as for quotients w.r.t. subquotients. So the same mechanism should do the job (see sage.categories.quotients.Quotients.default_super_categories). Please confirm!

Thanks. Done.

I see the point. The inconvenient is of course that this makes the set of homogeneous elements for a given i not be a vector space. What do you do with 0 btw?

Raise an error as previously for graded objects saying it doesn't have a well defined degree.


New commits:

bb234ecUse default_super_categories instead of extra_super_categories.

comment:4 follow-up: Changed 8 years ago by darij

1) What does the _element_constructor_ in associated_graded.py do? I understand that it constructs an element of gr A from an element a of A, but the way it does this I do not think is correct.

The "right" thing to do is this: For a given pair (a, n) where n is a nonnegative integer and a is an element of the n-th filtered part of A, the residue class of a modulo the (n-1)-th filtered part of A is an element of the n-th graded component of \gr A. The n is part of the input; you can try to reconstruct it as the smallest i such that a lies in the i-th filtered part of A, but such a definition will be ill-behaved.

2) I think you need some requirements on the basis of a FilteredModulesWithBasis? for your code to work. I would guess you want the basis to be a sequence (B_0, B_1, B_2, ...) of sets such that for every n, the union B_0 \cup B_1 \cup ...\cup B_n is a basis of the n-th filtered component. Is it what you want?

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

Replying to darij:

1) What does the _element_constructor_ in associated_graded.py do? I understand that it constructs an element of gr A from an element a of A, but the way it does this I do not think is correct.

The "right" thing to do is this: For a given pair (a, n) where n is a nonnegative integer and a is an element of the n-th filtered part of A, the residue class of a modulo the (n-1)-th filtered part of A is an element of the n-th graded component of \gr A. The n is part of the input; you can try to reconstruct it as the smallest i such that a lies in the i-th filtered part of A, but such a definition will be ill-behaved.

Hmmm....maybe this shouldn't be a coercion then since if ab = c1 + c2 (where deg(c1) > deg(c2)), then G(ab) != G(c1) + G(c2). The implementation of _element_constructor_ is definitely the right conversion however (the natural vector space isomorphism). So I'll remove the coercion part but leave the _element_constructor_.

2) I think you need some requirements on the basis of a FilteredModulesWithBasis? for your code to work. I would guess you want the basis to be a sequence (B_0, B_1, B_2, ...) of sets such that for every n, the union B_0 \cup B_1 \cup ...\cup B_n is a basis of the n-th filtered component. Is it what you want?

No, the basis does not have to be ordered with respect to the degree. I also don't see where in the code this is used (I just moved it over from the graded modules, so I may not have looked hard enough).

comment:6 follow-up: Changed 8 years ago by darij

That _element_constructor_ definitely shouldn't be a coercion, but even not being a coercion it should be surrounded with big fat warning signs for not being what one would expect.

I don't understand your answer to 2). Even your own doc says that the basis is graded:

+ def basis(self, d=None):
+ """
+ Return the basis for (an homogeneous component of) ``self``.

This means precisely that the basis elements have nonnegative integers ascribed to them, which stand for something like degree.

Generally, it seems to me that your filtered modules are precisely the same as graded modules, and only the richer "sub"categories (filtered algebras, filtered coalgebras etc.) differ from their graded counterparts. If so, this is a perfectly fine design decision, but it would help to document it explicitly.

comment:7 in reply to: ↑ 6 ; follow-up: Changed 8 years ago by tscrim

Replying to darij:

That _element_constructor_ definitely shouldn't be a coercion, but even not being a coercion it should be surrounded with big fat warning signs for not being what one would expect.

You wouldn't expect it to be the canonical linear isomorphism (as modules)? So given some x + y in the filtered algebra A, you wouldn't expect it to return x + y in gr A? Instead you'd want it to return only x (assuming it has larger degree)? This would be extremely surprising to me (we have a method to remove the lower order terms too). Or am I not understanding what you're saying?

I don't understand your answer to 2). Even your own doc says that the basis is graded:

+ def basis(self, d=None):
+ """
+ Return the basis for (an homogeneous component of) ``self``.

This means precisely that the basis elements have nonnegative integers ascribed to them, which stand for something like degree.

Well, any (additive) abelian group. Yet I'm not requiring that the i-th element of the basis be the only element of degree i. Again, an element is homogeneous of degree d if it belongs to Fd but not Fd-1. However I am requiring that Fd is a subspace.

Generally, it seems to me that your filtered modules are precisely the same as graded modules, and only the richer "sub"categories (filtered algebras, filtered coalgebras etc.) differ from their graded counterparts. If so, this is a perfectly fine design decision, but it would help to document it explicitly.

In my (naive) world, filtrations are not really different than grading for modules. That's not to say they aren't useful though because of things like I-adic topology (TBH, this is wikipedia talking). However I don't think we need doc on this. Nicolas, do you have any thoughts?

I could add something about the terminology for homogeneous in terms of the filtration if that's non-standard or unclear.

Question, should we make Weyl and Clifford algebras filtered on this ticket or on a followup since that's been closed? Same for group algebras by the length function.

comment:8 in reply to: ↑ 7 Changed 8 years ago by darij

Replying to tscrim:

Replying to darij:

That _element_constructor_ definitely shouldn't be a coercion, but even not being a coercion it should be surrounded with big fat warning signs for not being what one would expect.

You wouldn't expect it to be the canonical linear isomorphism (as modules)? So given some x + y in the filtered algebra A, you wouldn't expect it to return x + y in gr A? Instead you'd want it to return only x (assuming it has larger degree)? This would be extremely surprising to me (we have a method to remove the lower order terms too). Or am I not understanding what you're saying?

Well, I wouldn't expect to have any map from A to gr(A) when A is a filtered module/algebra, and the closest thing that comes to such a map would be a sequence of maps p_0, p_1, p_2, ... where p_n sends degree-\leq n elements of A to the n-th graded component of gr(A). However, when A is a filtered module/algebra *with basis*, then your _element_constructor can be viewed as a canonical map from A to gr(A) indeed (it depends on the basis, but this is no problem because the basis is part of A's data). You may find this a squeamish distinction, but the way most algebraists think about filtrations is not the way you do. For most algebraists, a filtered algebra has an associated graded algebra even if it does not have a basis or has several natural bases; and when things depend on a choice of basis, one regards these things as properties of the basis rather than properties of the algebra. This is why I want you to document this all so carefully.

Well, any (additive) abelian group. Yet I'm not requiring that the i-th element of the basis be the only element of degree i.

Oh! I think we misunderstood each other here.

In my (naive) world, filtrations are not really different than grading for modules.

Once again, this is good (I think this is the best we can do explicitly in a CAS, whereas the algebraists' notion of a filtered algebra would be some indiscrete lazy object) -- but this absolutely needs to be doced. This is plainly not the way algebraists think.

Question, should we make Weyl and Clifford algebras filtered on this ticket or on a followup since that's been closed? Same for group algebras by the length function.

Followup, definitely. The ticket has been closed already and I don't think this one will be done too quickly.

comment:9 Changed 8 years ago by git

  • Commit changed from bb234ec71d1276c6cc14320074b3de6fdc606192 to 5f6337908a43200ef3283e6dd24f4f6c6da66ee9

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

2ff607aMerge branch 'develop' into public/categories/filtered_algebras-17096
5f63379Addressing Darij's comments.

comment:10 Changed 8 years ago by git

  • Commit changed from 5f6337908a43200ef3283e6dd24f4f6c6da66ee9 to 2aec8bdaeba3c34478807342b5659b8e8ceca2f4

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

2aec8bdFixing some typos.

comment:11 Changed 8 years ago by tscrim

Okay, I've put in some comments about the translation A <-> gr A (it actually wasn't a coercion to begin with) and defined some terms. If you feel anything more needs to be doc'ed, then could you add it in since I'm not sure what more you think is needed?

Although I think there is still a module isomorphism which sends G_i -> F_i - F_{i-1} (since I require each F_i to be a module. Perhaps I'm missing something subtle (and I can't really think in coordinate-free terms very well).

comment:12 Changed 8 years ago by darij

I think your doc is inconsistent. This can't be:

+We require all `F_i \setminus F_{i-1}` to be modules for all `i`.

What do you want F_i to be? The span of all elements UP TO degree i, or the span of all elements that are added by degree i? So when you consider a graded module as a filtered module, then will F_i be the i-th graded component or the direct sum of the 0, 1, ..., i-th graded components? In the former case, you don't want a setminus at all. In the latter case, setminus is the right idea but the wrong notation, and you want to say something like F_i = F_{i-1} \oplus G_i where G_i is the submodule spanned by the degree i-basis elements.

comment:13 Changed 8 years ago by tscrim

For filtered algebras, we (only) have F0 <= F1 <= ..., so for graded modules, we'd have Gi = Fi - Fi-1 because we want that construction of Fi = Fi-1 (+) Gi (starting with F0 = G0). Actually, there is something that is wrong; the setminus isn't correct because it removes 0. It should be a quotient Fi / Fi-1, but other than that, it's consistent.

comment:14 Changed 8 years ago by git

  • Commit changed from 2aec8bdaeba3c34478807342b5659b8e8ceca2f4 to 592ba1176ae7a337c40792c0da3d439831ea3dc0

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

598f3c8Merge branch 'develop' into public/categories/filtered_algebras-17096
592ba11Some minor doc tweaks.

comment:15 Changed 8 years ago by git

  • Commit changed from 592ba1176ae7a337c40792c0da3d439831ea3dc0 to 60beb17df13f5399d9ce13f21984e903f77d3ea9

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

60beb17More explicit documentation.

comment:16 Changed 8 years ago by git

  • Commit changed from 60beb17df13f5399d9ce13f21984e903f77d3ea9 to 9d567ea2aaa030f51dbf2e966c8584bd2d8489ee

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

d75c90cMerge branch 'public/categories/filtered_algebras-17096' of git://trac.sagemath.org/sage into filter
9d567eaclarifying doc, or maybe obscuring it -- needs to be proofread

comment:17 Changed 8 years ago by darij

I have rewritten the doc to convey *my* understanding of your classes. It will probably have typos and wrong references -- sorry for that, I just can't manage to keep looking at sage categories for longer than a couple hours --, but if you see something that looks seriously wrong to you, chances are I have misunderstood your code and we need to discuss it over. I suspect I am not done with this patch either way, but I am going to return to tableaux and polytopes for a week or so.

I think there should be a one-stop shop in the doc to read up all of the (nonstandard but reasonable!) terminology around filtrations and gradings in Sage. Which should explain what "homogeneous" means for a filtered algebra, etc., and which should be referenced in the method-level and maybe even in the class-level docs. Where do you think such a thing would fit?

Also, there are two doctests failure that this patch incurs for some weird reason:

sage -t src/sage/categories/category_with_axiom.py
**********************************************************************
File "src/sage/categories/category_with_axiom.py", line 2513, in sage.categories.category_with_axiom.CategoryWithAxiom_singleton
Failed example:
    C.FiniteDimensional()
Expected:
    Category of finite dimensional connected test objects over base ring over Ring of integers modulo 2
Got:
    Category of finite dimensional test objects over base ring over Ring of integers modulo 2
**********************************************************************
File "src/sage/categories/category_with_axiom.py", line 2515, in sage.categories.category_with_axiom.CategoryWithAxiom_singleton
Failed example:
    C.Connected()
Expected:
    Category of connected test objects over base ring over Ring of integers modulo 2
Got:
    Category of test objects over base ring over Ring of integers modulo 2
**********************************************************************

Also, an easy one:

sage -t src/sage/categories/category.py
**********************************************************************
File "src/sage/categories/category.py", line 2627, in sage.categories.category.category_graph
Failed example:
    sage.categories.category.category_graph().plot()
Expected:
    Graphics object consisting of 312 graphics primitives
Got:
    Graphics object consisting of 324 graphics primitives
Last edited 8 years ago by darij (previous) (diff)

comment:18 Changed 8 years ago by git

  • Commit changed from 9d567ea2aaa030f51dbf2e966c8584bd2d8489ee to a11c501518c6785db1a99c78c04a1e38c2daff67

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

403b6adMerge branch 'develop' into public/categories/filtered_algebras-17096
198537cMerge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/categories/filtered_algebras-17096
a4bc65cFix failing doctests.
a15a170Made CliffordAlgebra into a filtered algebra.
41fbe5cMade Weyl algebra into a filtered algebra.
a11c501Documentation changes and added to docbuild.

comment:19 Changed 8 years ago by git

  • Commit changed from a11c501518c6785db1a99c78c04a1e38c2daff67 to 8e586e241a4365f8c21aa9d4f82fdcf920955b0a

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

8e586e2Merge branch 'develop' into public/categories/filtered_algebras-17096

comment:20 Changed 8 years ago by tscrim

I've fixed some things around, in particular, I made the definitions as general as possible. Because the basis for a filtered module are assumed to be homogeneous elements, the multiplication for the associated graded algebras is independent of the choice of basis. Actually, I'm pretty sure the important chunk of the assoc. graded algebras could be generalized for filtered algebras without a distinguished basis (or when the input is not a CombinatorialFreeModule), but I think that can wait. I also put Clifford and (Diff) Weyl algebras as filtered algebras because it was easy enough to do.

comment:21 Changed 8 years ago by darij

Can you go skype-on?

comment:22 Changed 8 years ago by git

  • Commit changed from 8e586e241a4365f8c21aa9d4f82fdcf920955b0a to 45aca1bb8e9492c4b076532a89c9334eec4dc1d2

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

45aca1bChanged some doc from conversation with Darij.

comment:23 Changed 8 years ago by git

  • Commit changed from 45aca1bb8e9492c4b076532a89c9334eec4dc1d2 to fe0e481ea01cf440ef5841f53ec9cb1a27d36862

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

fe0e481fixes to associated_graded.py

comment:24 Changed 8 years ago by git

  • Commit changed from fe0e481ea01cf440ef5841f53ec9cb1a27d36862 to b2bc6f59a7daf29f2e55fe0db40a241c06066b6e

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

b2bc6f5self.base_one removed

comment:25 Changed 8 years ago by git

  • Commit changed from b2bc6f59a7daf29f2e55fe0db40a241c06066b6e to b32aaf289e6a152a8938a87a6865d510d818bfb6

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

b32aaf2further review changes

comment:26 Changed 8 years ago by git

  • Commit changed from b32aaf289e6a152a8938a87a6865d510d818bfb6 to 68b47a88d9a650d3633f1b4ba3492b8a7bc3dabe

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

68b47a8Better return of algebra_generators for filtered alg w/ basis example.

comment:27 Changed 8 years ago by git

  • Commit changed from 68b47a88d9a650d3633f1b4ba3492b8a7bc3dabe to c3b29504eb8ec28ec0fe47b82ef59079f8f494c4

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

c3b2950enough for today

comment:28 Changed 8 years ago by darij

I have left a few TODOs in the doc, which would profit a lot from someone looking into them.

Note to self: I am at filtered_modules_with_basis.py.

comment:29 Changed 8 years ago by git

  • Commit changed from c3b29504eb8ec28ec0fe47b82ef59079f8f494c4 to b29f67e46e18721313330d3a6e116cf3df2eaf8e

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

2d29296Added option to consider the clifford algebra as filtered or graded.
b29f67eMerge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/categories/filtered_algebras-17096

comment:30 follow-up: Changed 8 years ago by darij

[Only a quick look at Clifford -- too swamped with work again.]

You implemented a graded_algebra method on the Clifford algebra; but does the algebra it return satisfy the contract of an associated graded algebra? Will it have the _element_constructor_, to_graded_conversion, from_graded_conversion and projection methods that allow one to relate its elements to the elements of the Clifford?

comment:31 in reply to: ↑ 30 Changed 8 years ago by tscrim

Replying to darij:

[Only a quick look at Clifford -- too swamped with work again.]

You implemented a graded_algebra method on the Clifford algebra; but does the algebra it return satisfy the contract of an associated graded algebra? Will it have the _element_constructor_, to_graded_conversion, from_graded_conversion and projection methods that allow one to relate its elements to the elements of the Clifford?

Currently there is no such contract (all graded algebras would not satisfy such a contract as well because they return themselves). However the _element_constructor_ and the natural conversion (projection) comes along for free (at least I believe it should, I didn't explicitly check).

comment:32 follow-up: Changed 8 years ago by darij

For the graded algebras returning themselves, this can -- and should -- be fixed. I think the contract is important -- the ass. gr. algebra without it is like a free algebra without a way to access its generators. Is it necessary to define the ass. gr. algebra of a filtered Clifford algebra to be the exterior algebra?

EDIT: On a second thought, maybe it is better to implement the projection and the back-and-forth isos not as methods on the ass. gr. algebra but as methods on the filtered algebra. This allows one and the same graded algebra to serve as the ass. gr. alegbra for several different filtered algebras. Would this make sense?

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

comment:33 in reply to: ↑ 32 ; follow-up: Changed 8 years ago by darij

Replying to darij:

For the graded algebras returning themselves, this can -- and should -- be fixed. I think the contract is important -- the ass. gr. algebra without it is like a free algebra without a way to access its generators. Is it necessary to define the ass. gr. algebra of a filtered Clifford algebra to be the exterior algebra?

EDIT: On a second thought, maybe it is better to implement the projection and the back-and-forth isos not as methods on the ass. gr. algebra but as methods on the filtered algebra. This allows one and the same graded algebra to serve as the ass. gr. alegbra for several different filtered algebras. Would this make sense?

Actually, these were bad ideas. Sorry, I don't think overwriting the graded_algebra method does any good, unless the return value is a refinement of what it would normally be (i.e., the AssociatedGradedAlgebra of self).

For an example why preserving a contract (and having a contract in the first place) is important, let's recall that gr is a functor. In fact, every filtration-preserving map f : A -> B of filtered modules induces a graded map gr f : gr A -> gr B of the associated gradeds. This map gr f sends the residue class of any a \in F_n(A) (this means the n-th filtered part of A) to the residue class of f(a) \in F_n(B). (This is *not* the map that would be obtained by composing the canonical iso gr A -> A with f : A -> B and then with the canonical iso B -> gr B when A and B are graded with basis. It is defined even without bases.) How would we implement this (on filtered modules or algebras with basis)? I would proceed like this:

def induced_graded_map(self, other, f):
    r"""
    Return the graded linear map ``self`` `\to` ``other`` canonically
    induced by a linear map `f` from the filtered module whose
    associated graded module is ``self`` to the filtered module whose
    associated graded module is ``other``.

    [...]

    """
    # not tested
    A = self._A # This requires ``self`` to have a ``_A`` attribute,
                # which must be part of the contract.
    def on_basis(m):
        i = self.degree_on_basis(m)
        # This needs a ``degree_on_basis`` method on ``self``.
        return other.projection(i)(f(A.monomial(m)))
        # This needs the ``projection`` method to exist on
        # ``other``.
        # This assumes that the basis element of ``A`` indexed
        # by ``m`` is a lift of the basis element of ``self``
        # indexed by ``m``. This is a fairly harmless assumption.
    return self.module_morphism(on_basis=on_basis,
                                codomain=other, category=self.category())
    """

This is a piece of code so basic and general that it should be in associated_graded.py. But if we start redefining graded_algebra in ways that remove its _A attribute, its projection method and whatever else, then this code breaks.

I suck at Python OOP; do you know a way to take an existing instance of AssociatedGraded and add some methods to it? If this is possible, then I think this is what overrides of graded_algebra should be doing. For instance, the graded algebra of a Clifford algebra should be its AssociatedGraded, but with a coercion to and from the exterior algebra.

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

comment:34 Changed 8 years ago by nbruin

Don't forget that code like this (which initializes default categories):

+ if graded:
+     category = AlgebrasWithBasis(R).Graded()
+ else:
+     category = AlgebrasWithBasis(R).Filtered()

should do instead AlgebrasWithBasis(R.category()) to avoid a certain source of memory leaks: categories are immortal, so you should avoid making potentially arbitrarily many of them as much as possible. See:

sage: GF(3)['x'].category()
Join of Category of euclidean domains and Category of commutative algebras over (finite fields and subquotients of monoids and quotients of semigroups)

Once someone asks for [AlgebrasWithBasis(GF(p)): p in prime_range(2,100000)] they're in it by choice, but by default we should not be making categories that explicitly refer to parametrized quantities. We can store those in the parents themselves, where avoiding memory leaks is hard enough. The design of categories simply didn't take into account that they might need to be collected again.

See #17360 for a similar category initialization problem.

Last edited 8 years ago by nbruin (previous) (diff)

comment:35 Changed 8 years ago by jhpalmieri

A few questions and comments:

  • in filtered_modules.py, it talks about modules over a commutative ring, but the word "commutative" can be deleted, I think.
  • in the same file, it says
    .. TODO::
    
        Implement a notion for decreasing filtrations: where `F_j \subseteq F_i`.
    
    If you want to keep this remark, then you should add "when i \leq j". But do you need to keep this? If you want a decreasing filtration, just use the non-positive integers for your indexing set instead of non-negative integers. For example, if you have an algebra A and an ideal I, then you can set F_{-n}A equal to the nth power of I. Then you have F_0 \supseteq F_{-1} \supseteq F_{-2} \supseteq ...: a decreasing filtration.
  • How could we implement an algebra which is both graded and filtered? This is the situation for the Steenrod algebra, for example.

comment:36 Changed 8 years ago by darij

I have edited my latest reply.

In other news, is it guaranteed that every instance of FilteredAlgebrasWithBasis is a subcategory of FilteredModulesWithBasis? If so, I suggest moving the ElementMethods is_homogeneous, homogeneous_degree, degree and maximal_degree out of the algebras class and into the modules class (merging their doctests in case both exist).

The associated-graded construction should also be defined for modules rather than algebras; the algebras version should be a refinement that additionally gives a multiplication and a unity. Can this be implemented easily in your framework, Travis?

comment:37 follow-ups: Changed 8 years ago by tscrim

@darij I really don't like the restrictions of this contract you want to impose; it's too restrictive. It should not take a new *class* to do something which is mathematically trivial (by our current implementation of an implicit filtration). IMO, the better way to do things is to implement additional methods in the category for the projections (similar to truncate) since the methods only use the degree methods. Also I think requesting a conversion for the returned object graded_algebra is fine, but not making it a requirement.

As for the induced morphisms, we might actually want to make the method a functor object. This I think will solve many of the issues you want to do with contracts.

All I wanted with the AssociatedGradedAlgebra class was to prove a generic implementation do to the computations and the method graded_algebra just to return an object which *is* the associated graded algebra. My implementation of AssociatedGradedAlgebra just happens to have the need for the extra data.

Every FilteredAlgebrasWithBasis is a subcategory of FilteredModulesWithBasis. I'm okay with this move. If we use methods (instead of contracts) at the FilteredModules level (perhaps WithBasis), then we could implement a very lightweight class for this, but I'm worried about having the extra burden of methods that only are really useful for modules (and get superseded for "better" named methods). Although if we use a functor to do the construction, then I feel like we get away from all of it.

However I feel that much of this should be done on followup ticket(s) as getting the basic framework into Sage can be split and doesn't need the full features to be useful.

@jhpalmieri I'll make those changes. However we can't get a descending filtration unless the grading set can be negated. As for algebras that are both filtered and graded, it's the same issue as when an algebra has 2 natural gradings (as we use degree for both filtration and grading). Although as things evolve and the filtration can be generalized from using degree, this can be rectified. For now, you have to choose the "best" one for degree (or have it be an optional arg like how I'm doing for Clifford algebras).

@nbruin Will fix. Forgot that the categories are not collectible.

comment:38 Changed 8 years ago by jhpalmieri

I'll make those changes. However we can't get a descending filtration unless the grading set can be negated.

You can get something mathematically equivalent to a descending filtration, though, and maybe that should be good enough?

I wonder if we should use degree for grading and filtration for a filtration: x.filtration() would return n if x is in F_n but not in F_{n-1}. For a filtered object, degree would default to be filtration, but you could override it in any specific case. (Maybe these aren't the best names, but you get the idea.)

If this is the first ticket with filtrations, at least in any systematic way, we can decide how to set it up now rather than having to fix it later.

comment:39 in reply to: ↑ 37 ; follow-up: Changed 8 years ago by darij

Replying to tscrim:

@darij I really don't like the restrictions of this contract you want to impose; it's too restrictive. It should not take a new *class* to do something which is mathematically trivial (by our current implementation of an implicit filtration). IMO, the better way to do things is to implement additional methods in the category for the projections (similar to truncate) since the methods only use the degree methods.

Care to elaborate how this will work?

comment:40 in reply to: ↑ 39 Changed 8 years ago by tscrim

Replying to darij:

Care to elaborate how this will work?

Move to_graded_conversion, from_graded_conversion, and projection into FilteredModulesWithBasis. This would have the effect of reversing the meaning of to/from, but it would make me feel better that the morphisms are tied to the domain (whereas putting them in the graded part, they would be tied to the codomain, making the maps collectible and can cause the coercion issues). Plus it gives a natural extension to GradedModulesWithBasis and you could use the homogeneous_component method to construct the projection method.

In fact, if we do this properly, we can have a category for algebras whose associated graded is commutative (I thought this was called something like virtually commutative, but I can't find where I saw this...) where we can use a faster generic implementation. Again, something for later.

comment:41 follow-up: Changed 8 years ago by darij

Ah! This is a good idea; then induced_graded_map will also have to be moved to the filtered algebra class. Can you move the three methods you mentioned please? I will then implement induced_graded_map.

So let me get it right: The class AssociatedGraded is not going to be a class to be inherited from; it will plainly be the way to construct associated graded algebras if nothing better is known. The data connecting gr(A) to A will be stored on A rather than on gr(A). I assume it makes sense to make graded_algebra a cached method to avoid cases where it is not UniqueRepresentation?

Also, could you reply to my post 36? I don't see FilteredAlgebrasWithBasis ever mentioning FilteredModulesWithBasis as a supercategory, but I guess it should, and I guess its methods should be on FilteredModulesWithBasis as well.

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

comment:42 in reply to: ↑ 41 ; follow-ups: Changed 8 years ago by tscrim

Replying to darij:

Ah! This is a good idea; then induced_graded_map will also have to be moved to the filtered algebra class. Can you move the three methods you mentioned please? I will then implement induced_graded_map.

Will do tomorrow, but will do (plus incorporate John's and Nils' changes).

So let me get it right: The class AssociatedGraded is not going to be a class to be inherited from; it will plainly be the way to construct associated graded algebras if nothing better is known. The data connecting gr(A) to A will be stored on A rather than on gr(A). I assume it makes sense to make graded_algebra a cached method to avoid cases where it is not UniqueRepresentation?

Yes, that's correct (although it could be subclasssed but that's not my intent when I designed it). However it doesn't need to be a cached method because everything comes along for the ride from the category (and it should return an equal object every time). Nils, does this lead to a memory leak when a @cached_method return a UniqueRepresentation? I think it does but I don't remember...

Also, could you reply to my post 36? I don't see FilteredAlgebrasWithBasis ever mentioning FilteredModulesWithBasis as a supercategory, but I guess it should, and I guess its methods should be on FilteredModulesWithBasis as well.

I did in comment:37 and said it was okay with me to move the methods. It's the category and axiom magic which makes the supercategory property hold.

comment:43 in reply to: ↑ 42 ; follow-up: Changed 8 years ago by darij

Replying to tscrim:

Yes, that's correct (although it could be subclasssed but that's not my intent when I designed it). However it doesn't need to be a cached method because everything comes along for the ride from the category (and it should return an equal object every time).

Care to explain this? I'm still a newbie to memory handling, so I might be missing more of the context than you expect. My worry was that every time A.graded_algebra() is called (and it will be called a lot, say, from the to_graded_conversion and projection methods), a new instance of this algebra is created, which takes time and space and might require additional work to make these instances coerce to each other nicely (I guess they will do so themselves automatically, but e.g. their polynomial rings might not).

Also, should I then explain in the doc that everybody who overshadows graded_algebra must also overshadow projection, to_graded_conversion and from_graded_conversion?

I did in comment:37 and said it was okay with me to move the methods. It's the category and axiom magic which makes the supercategory property hold.

Great -- as long as this magic doesn't force every algebra which happens to be filtered as a module to automatically be considered a filtered algebra.

comment:44 in reply to: ↑ 42 Changed 8 years ago by nbruin

Replying to tscrim:

Yes, that's correct (although it could be subclasssed but that's not my intent when I designed it). However it doesn't need to be a cached method because everything comes along for the ride from the category (and it should return an equal object every time). Nils, does this lead to a memory leak when a @cached_method return a UniqueRepresentation? I think it does but I don't remember...

Quite possibly. See #14356 comment 6 and https://groups.google.com/forum/#!msg/sage-devel/q5uy_lI11jg/CB15fcRmE4cJ

The main thing to watch out for is caching on an object A a UniqueRepresentation object B that has A as a construction parameter.

As pointed out in the referenced comment, one is usually in the clear if the construction parameters of a UniqueRepresentation are fundamentally simpler than the object itself. I'd say that fails for AssociatedGradedAlgebra if that takes an algebra it's isomorphic to as an ungraded algebra as construction parameter! I would consider making it a factory and construct from only the base ring, generator names, grading information etc. and then link it via the coercion framework/cached methods. Then at least it's clear that strong references are held locally. It's important to realize that UniqueRepresentation has a serious cost associated with it.

comment:45 Changed 8 years ago by git

  • Commit changed from b29f67e46e18721313330d3a6e116cf3df2eaf8e to 096538121130679a55b971d3d3a5626e94b157a5

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

0965381Changes from discussion on trac.

comment:46 in reply to: ↑ 43 ; follow-up: Changed 8 years ago by tscrim

Replying to darij:

Care to explain this? I'm still a newbie to memory handling, so I might be missing more of the context than you expect. My worry was that every time A.graded_algebra() is called (and it will be called a lot, say, from the to_graded_conversion and projection methods), a new instance of this algebra is created, which takes time and space and might require additional work to make these instances coerce to each other nicely (I guess they will do so themselves automatically, but e.g. their polynomial rings might not).

See Nils comment for the memory. Short version is you get a reference loop A -> grA and grA -> A such that A is stored as a global strong reference (making it uncollectible). I opted to make the output of graded_algebra be a non-cached_method as the UniqueRepresentation of AssociatedGradedAlgebra will make sure it's extremely rarely (re)created (and because I need the filtered algebra to do the computations, so it has to be part of the construction data). As this will likely be what gets created, we don't have to worry about this (and most parents will end up being UR's). If the user creates a non-UR parent for the assoc. gr., then they have to override graded_algebra anyways and can make it a cached method.

Also, should I then explain in the doc that everybody who overshadows graded_algebra must also overshadow projection, to_graded_conversion and from_graded_conversion?

I don't think these methods would need to be overwritten as they are completely generic.

Great -- as long as this magic doesn't force every algebra which happens to be filtered as a module to automatically be considered a filtered algebra.

I think that gets into the issue (and is related with John's comment) with what do for filtrations in general. I want to use degree for the filtration parameter so we don't have to duplicate code, it's natural for graded modules/algebras, and which filtration component is not well-defined (most elements belong to multiple, possibly infinite, Fi components). Overall, we will need a framework for construction of general filtrations, but I don't think we can do that at the category level. What will probably be best (a quick thought) is to have a method filtration which returns the filtration of the module/algebra as a Family of submodules indexed by I. However we will still need a method degree to be computationally quick. This would allow filtrations different from the grading in a way and perhaps we could add a method to the graded categories such as filtration_degree which by default returns the usual degree. Anyways, I think about more later.

comment:47 in reply to: ↑ 46 ; follow-up: Changed 8 years ago by darij

Replying to tscrim:

Also, should I then explain in the doc that everybody who overshadows graded_algebra must also overshadow projection, to_graded_conversion and from_graded_conversion?

I don't think these methods would need to be overwritten as they are completely generic.

What do you mean by this?

Anyway, should I continue the review or are you still working on the changes?

comment:48 in reply to: ↑ 47 Changed 8 years ago by tscrim

Replying to darij:

Replying to tscrim:

I don't think these methods would need to be overwritten as they are completely generic.

What do you mean by this?

I mean we only need the methods defined in the category, so it's generic in that sense (i.e. independent of implementation).

Anyway, should I continue the review or are you still working on the changes?

I'm done making changes; please continue.

comment:49 Changed 8 years ago by git

  • Commit changed from 096538121130679a55b971d3d3a5626e94b157a5 to 79894b4c5b248281fbba1b932171b18a59e5b137

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

3a9e4e9Merge branch 'public/categories/filtered_algebras-17096' of git://trac.sagemath.org/sage into filnew
79894b4filtered_modules(_with_basis).py reviewed -- see TODOs

comment:50 Changed 8 years ago by git

  • Commit changed from 79894b4c5b248281fbba1b932171b18a59e5b137 to 25c0fbc2e1c75e4d1a255ca41d4d6235b4571453

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

25c0fbclooked through clifford_algebra and filtered_algebras*; many TODOs left

comment:51 Changed 8 years ago by git

  • Commit changed from 25c0fbc2e1c75e4d1a255ca41d4d6235b4571453 to 2a62c3b093a2a991422f8c4f261d1a9d5ac6e059

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

2a62c3blift_* methods in algebras/clifford_algebra.py should remember the graded-filtered choice

comment:52 Changed 8 years ago by git

  • Commit changed from 2a62c3b093a2a991422f8c4f261d1a9d5ac6e059 to 15cf0dce22ece06760fdd270257f98757625f0a9

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

15cf0dcfix and a first doctest for induced_graded_map

comment:53 Changed 8 years ago by git

  • Commit changed from 15cf0dce22ece06760fdd270257f98757625f0a9 to 50299560bf500b649aa5bdc3e7c7690fa09e2fb1

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

5029956another pitfall documented

comment:54 Changed 8 years ago by git

  • Commit changed from 50299560bf500b649aa5bdc3e7c7690fa09e2fb1 to 292ef5f2a26bff5302a5d97ebf22d34240c78f72

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

292ef5fanother doctest

comment:55 Changed 8 years ago by darij

Done for today. I'll add some more doctests tomorrow and hopefully get to read through the rest of the files, although I'd much prefer if you get rid of some of the TODOs beforehand. I'll then try to generalize graded_algebra and AssociatedGraded to filtered modules (not just filtered algebras); IMHO this is a highly natural step to do.

If the Clifford issues become too complicated, what do you think of splitting this patch into a general filtrations one and a Clifford one? I see nontrivial work ahead in both of them, so a split would speed up the merge of the general code.

comment:56 Changed 8 years ago by git

  • Commit changed from 292ef5f2a26bff5302a5d97ebf22d34240c78f72 to c2e84e1367cbfc47eb7104de654e2ee55caea95d

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

c2e84e1remaining doctests for induced_graded_map

comment:57 Changed 8 years ago by git

  • Commit changed from c2e84e1367cbfc47eb7104de654e2ee55caea95d to 03bd4cfb53e24b24c65aada21f08850b40fb5c5c

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

03bd4cfpossibly controversial: graded_algebra and the three methods forming its interface are now cached_methods

comment:58 Changed 8 years ago by darij

Another issue with the Clifford-Weyl part of this patch: The Clifford algebra is graded by default, whereas the Weyl algebra is graded by default. There is no reason why there should be different behavior here; the Weyl algebra is Z/2-graded as much as the Clifford one is.

comment:59 Changed 8 years ago by git

  • Commit changed from 03bd4cfb53e24b24c65aada21f08850b40fb5c5c to 8a747c073e706950d1b14e77458539e126ff0550

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

8a747c0further edits

comment:60 Changed 8 years ago by darij

Enough for now (FPSAC deadline is approaching). I have now checked all of the non-Clifford/Weyl? part of this patch, and here is all that I'd like to be done before the merge of this part:

  • TODO: Formulate an interface and a contract for FilteredModulesWithBasis objects. Is a CombinatorialFreeModule with a degree_on_basis method enough? Or is basis still needed? (See the FIXME in src/sage/categories/examples/filtered_modules_with_basis.py.)
  • TODO: Make sense of A.basis(d) for A a filtered module and d an integer. This has always been broken and we can leave it for later, but it then needs a trac ticket.
  • TODO: doctesting A.basis(d) for A graded. Very easy once above is fixed.
  • TODO: overriding the to_graded_conversion, from_graded_conversion and projection methods on graded algebras for the sake of speed, or deciding not to. [EDIT: This would be difficult with the current design.]
  • [DONE:] Generalizing graded_algebra to modules. This doesn't seem too difficult; I am in favor of keeping the name "associated graded *algebra*" even for modules, as it seems to have a ring to it that algebraists recognize, but maybe some discussion is in order.

On the Clifford/Weyl? front, I'll review it once you deal with the TODOs and the Clifford-Weyl mismatch; the changes IMHO are nontrivial enough (and orthogonal to the categories themselves) to warrant an extra ticket. (I'll need to check through all the methods in the two files.)

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

comment:61 in reply to: ↑ 37 ; follow-up: Changed 8 years ago by jhpalmieri

Replying to tscrim:

@jhpalmieri I'll make those changes. However we can't get a descending filtration unless the grading set can be negated. As for algebras that are both filtered and graded, it's the same issue as when an algebra has 2 natural gradings (as we use degree for both filtration and grading). Although as things evolve and the filtration can be generalized from using degree, this can be rectified. For now, you have to choose the "best" one for degree (or have it be an optional arg like how I'm doing for Clifford algebras).

I still don't understand this design choice. Why not separate filtrations and gradings? A graded object without additional filtration could still be considered to be filtered (by having the filtration method default to calling degree), but this wouldn't have to be the only choice.

Replying to darij:

Generalizing graded_algebra to modules. This doesn't seem too difficult; I am in favor of keeping the name "associated graded *algebra*" even for modules, as it seems to have a ring to it that algebraists recognize, but maybe some discussion is in order.

"Have a ring to it". Heh.

I would object to calling a module an "algebra" if there is no multiplicative structure. "Associated graded module" is just fine, or "associated graded object" more generally.

comment:62 in reply to: ↑ 61 ; follow-up: Changed 8 years ago by darij

Replying to jhpalmieri:

I still don't understand this design choice. Why not separate filtrations and gradings? A graded object without additional filtration could still be considered to be filtered (by having the filtration method default to calling degree), but this wouldn't have to be the only choice.

How do you suggest separating them?

(In a better language, there would be a way to handle this using some kind of aliases. Note that there are many modules and algebras in nature having multiple filtrations, so just creating a slot for a grading and a slot for filtrations doesn't seem like a scalable solution to me.)

@nbruin: I only really digested your post right now. So my changes do cause memleaks. OK, nothing easier than removing some @cached_method decorators. But... can you look at the code for induced_graded_map and tell me how to avoid having it re-construct the other.projection(i) method every time I call its return value? (And while the ass. gr. algebra itself might be UniqueRepresentations?, things like the projection map are not unless we hash them.)

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

comment:63 Changed 8 years ago by jhpalmieri

When you initialize a filtered object, you could pass an argument saying how it is filtered:

FilteredObject(A, filtration=fcn)

where A is an object and fcn is a function which takes an element of A as input and returns an element of the filtering monoid. (Change 'object' to 'algebra', 'module', 'group', 'ring', throughout if you'd rather.) So a simple example could be

FilteredObject(A, filtration=degree)

but you could also have

FilteredObject(A, filtration=smith_filtration)
FilteredObject(A, filtration=lambda x: 2 + 3*x.jones_filtration())
FilteredObject(A, filtration=lambda x: 0 if x.is_zero() else Infinity)
...

One point is that, even if an object has many possible filtrations, when you consider it as a filtered object, you are at that point choosing a filtration. It's like the difference between a Module and a ModuleWithBasis. I guess I should have called this ObjectWithFiltration instead? Anyway, it's not FilterableObject, allowing for multiple possible filtrations, it's FilteredObject.

If the filtration keyword is missing, then perhaps first you see if the Element class has a filtration method, and if not, you see if it has a degree method.

comment:64 follow-up: Changed 8 years ago by tscrim

How is that any different for objects with multiple natural gradings? The point I'm trying to make is GradedAlgebra is not an algebra that has some grading (all algebras have a trivial grading), but that they have a distinguished grading, just like (FiniteDimensional)AlgebrasWithBasis are algebras with a distinguished basis (can replace grading by filtered).

The main reason why I chose to use grading is so we don't have to duplicate all of the code for graded algebras but just replacing degree by smallest_filtered_component (or whatever name you want to call it).

For the Clifford algebras, we don't yet have the category framework in place (I know how I want to do it, but I haven't done so yet). Perhaps it is a bad choice to give Clifford algebras that option right now for the future outlook. Also now that we have the filtered algebras, we don't need the graded algebras to get extra features.

This relates to John's suggestion, and that we probably need something at the class level, not the category level which is what this ticket is about, which set's the degree function. I want to stress that the category has a distinguished filtration/grading (perhaps I forgot to reflect this in the documentation).

I will take a more detailed look at all of the changes later tonight.

comment:65 in reply to: ↑ 62 Changed 8 years ago by nbruin

Replying to darij:

@nbruin: I only really digested your post right now. So my changes do cause memleaks. OK, nothing easier than removing some @cached_method decorators. But... can you look at the code for induced_graded_map and tell me how to avoid having it re-construct the other.projection(i) method every time I call its return value? (And while the ass. gr. algebra itself might be UniqueRepresentations?, things like the projection map are not unless we hash them.)

Yes, that's tricky. I didn't read the code in detail, but in general I would expect that with caching maps on objects that use each other as construction parameters, you do end up with the problematic reference cycles, rooted in a global cache reference.

If your projection can somehow be obtained as a coercion/conversion you may be able to lift on the effort that went in there (internally, those maps drop their reference to the domain now. Since they are normally cached on the codomain, that seems to usually be enough to break cycles).

I don't have a proof of the following, but conceptually it seems reasonable to me that you can choose one of the following approaches, but that mixing them will lead to memory leaks:

  • either you express the relation between objects by using one as a UniqueRepresentation parameter for the other and you rely entirely on that relation to tie the objects together
  • or you manage the link yourself, by caching stuff on the objects. In the latter case, you should *not* let any of the globally cached construction parameters refer to the objects involved. That will usually mean using UniqueFactory rather than UniqueRepresentation, so that you can process the keys a bit.

I suspect that what we need is that there is a partial ordering on our globally cached objects, where A<B if A can occur as part of a construction cache key for B. Having both A<B and B<A would naturally lead to a reference cycle and hence a leak.

Furthermore, if A<B and A holds a strong reference to B in any form then there's a leak too.

For instance QQ can be a construction parameter of QQ[x] because QQ does not refer to QQ[x] in any way (the fact that QQ coerces into QQ[x] is stored on QQ[x]).

In the case here, where I think we have things like A=CommutativeAlgebra(QQ,['x','y','z']) and B=GradedCommutativeAlgebra(QQ,['x','y','z']) it is not clear if we should have A<B or B<A. So I think we should have neither (the constructions above definitely don't need it) and then you're free to cache on these things in either direction, provided you don't coerce (:-)) the coercion framework into holding a reference cycle.

In hindsight I really think UniqueRepresentation is a mistaken design decision. We sort of need it for efficient coercion, though.

comment:66 follow-up: Changed 8 years ago by darij

@nbruin: Thanks for the explanations. So it is what I feared. Someone please remove the @cached_methods; it appears there is no easy way to get rid of the performance issues.

Caching these maps relating A to gr(A) on gr(A) was my first idea (and I think Travis wanted to implement them as conversions), but it conflicts with Travis's design decision (which is a good one!) to allow overriding graded_algebra with simpler stuff than the default AssociatedGraded construction. Many different complicated algebras A will end up having the same simple gr(A) (for example, for every universal enveloping algebra A = U(g) of a Lie algebra g over a field, we have gr(A) \cong S(g)), and gr(A) is not supposed to "know" anything about A. Overriding _element_constructor of gr(A) would be messy and unscalable.

comment:67 in reply to: ↑ 64 ; follow-up: Changed 8 years ago by jhpalmieri

Replying to tscrim:

How is that any different for objects with multiple natural gradings?

It's the same issue.

The main reason why I chose to use grading is so we don't have to duplicate all of the code for graded algebras but just replacing degree by smallest_filtered_component (or whatever name you want to call it).

My main concern is that I want to be able to have a graded algebra with an additional filtration on it (ideally so that the associated graded algebra is bigraded). I think you said (or someone said) that this could be done with some reworking of the code in this branch. If that's accurate, then it seems like it would be better to have more flexible code that could handle this right from the start, instead of implementing it one way and then rewriting it later on.

comment:68 in reply to: ↑ 66 ; follow-up: Changed 8 years ago by nbruin

Replying to darij:

Caching these maps relating A to gr(A) on gr(A) was my first idea (and I think Travis wanted to implement them as conversions), but it conflicts with Travis's design decision (which is a good one!) to allow overriding graded_algebra with simpler stuff than the default AssociatedGraded construction. Many different complicated algebras A will end up having the same simple gr(A) (for example, for every universal enveloping algebra A = U(g) of a Lie algebra g over a field, we have gr(A) \cong S(g)), and gr(A) is not supposed to "know" anything about A. Overriding _element_constructor of gr(A) would be messy and unscalable.

That suggests that gr(A) should be the simpler object. I'm not sure you want to go as far as having gr(A)<A, but it does strongly suggest you don't want A<gr(A). You're saying yourself that gr(A) is not supposed to "know" about A. That implies that A is not a construction parameter for gr(A). Instead, gr(A) should be constructed from basic parameters that can be retrieved from A. Mind you, that doesn't preclude the existence of an interface function GradedAlgebra(A), but instead of being a UniqueRepresentation class constructor, it would be a factory function that creates the relevant object from the relevant parameters from A.

Whether the coercion from A to gr(A) should then be managed by an "embedding" (that's coercion stored on A) is a different question. There is a good potential for creating memory leaks via those too.

comment:69 in reply to: ↑ 67 Changed 8 years ago by tscrim

Replying to jhpalmieri:

It's the same issue.

Okay, we're on the same page. I think the solution is the same.

My main concern is that I want to be able to have a graded algebra with an additional filtration on it (ideally so that the associated graded algebra is bigraded). I think you said (or someone said) that this could be done with some reworking of the code in this branch. If that's accurate, then it seems like it would be better to have more flexible code that could handle this right from the start, instead of implementing it one way and then rewriting it later on.

I spoke off-hand that there might be a good way to do this as the code evolved. With some more thought, I think if you have degree return (f, g) where f is the filtration and g the grading, then it should handle things properly in the same was if you were trying to construct a bigraded algebra.

comment:70 in reply to: ↑ 68 Changed 8 years ago by tscrim

Replying to nbruin:

Replying to darij:

Caching these maps relating A to gr(A) on gr(A) was my first idea (and I think Travis wanted to implement them as conversions), but it conflicts with Travis's design decision (which is a good one!) to allow overriding graded_algebra with simpler stuff than the default AssociatedGraded construction. Many different complicated algebras A will end up having the same simple gr(A) (for example, for every universal enveloping algebra A = U(g) of a Lie algebra g over a field, we have gr(A) \cong S(g)), and gr(A) is not supposed to "know" anything about A. Overriding _element_constructor of gr(A) would be messy and unscalable.

That suggests that gr(A) should be the simpler object. I'm not sure you want to go as far as having gr(A)<A, but it does strongly suggest you don't want A<gr(A). You're saying yourself that gr(A) is not supposed to "know" about A. That implies that A is not a construction parameter for gr(A). Instead, gr(A) should be constructed from basic parameters that can be retrieved from A. Mind you, that doesn't preclude the existence of an interface function GradedAlgebra(A), but instead of being a UniqueRepresentation class constructor, it would be a factory function that creates the relevant object from the relevant parameters from A.

Whether the coercion from A to gr(A) should then be managed by an "embedding" (that's coercion stored on A) is a different question. There is a good potential for creating memory leaks via those too.

It's not true that gr(A) is (suppose to be) independent of A. The multiplication of gr(A) is defined from the multiplication in A (plus the imposed filtration). However, that's not to say we can't construct the associated graded algebra without appealing to A, but we're essentially just using specialize code. From that, I strongly believe we want A < gr(A), to the point that I'd want to implement gr as a Functor instance in a follow-up (at least, I'm pretty sure it is a functor).

comment:71 Changed 8 years ago by darij

You can't have A < gr(A) as long as you choose to identify (say) the ass. gr. of a Clifford algebra with an exterior algebra, and the ass. gr. of a graded algebra with itself.

comment:72 Changed 8 years ago by tscrim

Why not? There's nothing wrong with that. Technically we're saying there's no relation, but it's okay to remove relations from this poset.

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

comment:73 Changed 8 years ago by darij

When A is graded, how do you want A < A?

comment:74 Changed 8 years ago by tscrim

A is constructed from independent data and graded_algebra in that case does not construct any new objects. So there would be no A < A.

comment:75 Changed 8 years ago by darij

What do you mean by "A is constructed from independent data"? What if A is UniqueRep? and constructs itself? (Skype?)

comment:76 Changed 7 years ago by git

  • Commit changed from 8a747c073e706950d1b14e77458539e126ff0550 to 752df7798b2ae6b9afc60528227b4e88c745fae9

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

831c269Merge branch 'public/categories/filtered_algebras-17096' of git://trac.sagemath.org/sage into filt
752df77Revert the cached_method decorators from commit "possibly controversial: graded_algebra and the three methods forming its interface are now cached_methods"

comment:77 in reply to: ↑ 33 Changed 7 years ago by darij

  • Work issues set to comment:60 todo list

About why I think FilteredModulesWithBasis needs a contract:

Here are the methods on F that are used in the implementations of the methods of FilteredModulesWithBasis when F is cast as a FilteredModulesWithBasis:

ParentMethods:
degree_on_basis
sum_of_terms
monomial
_indices

ElementMethods:
support
leading_support
is_homogeneous
is_zero

I hear the quacking of a CombinatorialFreeModule duck here (except for degree_on_basis which should be explicitly required). Are there any more general categories which offer these methods?

comment:78 Changed 7 years ago by git

  • Commit changed from 752df7798b2ae6b9afc60528227b4e88c745fae9 to dfaaaeb6d9652e071ea89c9854da984bc8ada319

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

dfaaaebassociated-graded now also defined for filtered *modules*, although still named 'graded algebra' in this case

comment:79 Changed 7 years ago by darij

On the subject of associated graded objects of filtered *modules*, they are now implemented (see the doctests for why they are a useful notion -- it is really the induced_graded_map that makes them useful). But naming them graded_algebra is questionable, and I understand jhpalmieri's objections to it. What about renaming graded_algebra as associated_graded (for both modules and algebras)? Nicolas just suggested this and I like the idea.

(We algebraists don't have a good name for this notion. "Associated graded" is too long and an adjective that makes the listener search in vain for a noun. "gr" is too short and hard to pronounce.)

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

comment:80 Changed 7 years ago by darij

@Travis: here is the main thing I want you to address before I review the Clifford & Weyl stuff in this ticket:

Another issue with the Clifford-Weyl part of this patch: The Clifford algebra is graded by default, whereas the Weyl algebra is graded [oops: I meant filtered here] by default. There is no reason why there should be different behavior here; the Weyl algebra is Z/2-graded as much as the Clifford one is.

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

comment:81 Changed 7 years ago by tscrim

  • Dependencies set to #18044

As Darij and I discussed today, we should make Weyl and Clifford algebras super filtered algebras, so we need #18044.

comment:82 Changed 7 years ago by git

  • Commit changed from dfaaaeb6d9652e071ea89c9854da984bc8ada319 to 14e19ba97f1bb096c7614241c9b09c1d0f699a19

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

cd6d21aCreated super categories for algebras and modules.
3d33730Merge branch 'develop' into public/categories/super_categories-18044
43a976aMerge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/categories/filtered_algebras-17096
d1d135fGive Weyl/Clifford/Exterior super powers.
14e19baFixing doctests and updating documentation.

comment:83 Changed 7 years ago by git

  • Commit changed from 14e19ba97f1bb096c7614241c9b09c1d0f699a19 to 9bc28fd5fdbcb5463703739a9077886a113596a5

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

9bc28fdChanging abstract methods and doc based off talking with Nicolas.

comment:84 Changed 7 years ago by tscrim

  • Cc days64 added
  • Milestone changed from sage-6.4 to sage-6.6
  • Work issues comment:60 todo list deleted

I talk a bit about this ticket with Nicolas tonight, and we decided to not make support an abstract method right now, but instead leave a message in the category about this. We will fix support along with many other issues with an object in ModulesWithBasis being too close to a CombinatorialFreeModule in the followup #18066. I think with this we've handled everything from comment:60.

comment:85 Changed 7 years ago by git

  • Commit changed from 9bc28fd5fdbcb5463703739a9077886a113596a5 to 1404ad0e2336eee05877e3e1a434809d437a998d

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

160416218174: small doc improvements
710d09e18174: more doc improvements + uniformization with CategoryWithAxiom
0ce1cadChanging the wording of the Super method.
b29650bMade it so you must explicitly designate graded as a super category
f3bdf9bMerge branch 'public/categories/super_categories-18044' of trac.sagemath.org:sage into public/categories/super_categories-18044
19c3471Cleanup from adding #18044.
7554dbd1 step forward, 2 steps back.
caada13Going all the way to the finish line like a superstar.
d56ef84Merge branch 'public/categories/super_categories-18044' into public/categories/filtered_algebras-17096
1404ad0Cleanup from merged code.

comment:86 Changed 7 years ago by tscrim

  • Cc sd67 added

comment:87 Changed 7 years ago by git

  • Commit changed from 1404ad0e2336eee05877e3e1a434809d437a998d to f219ce3a60512bac0da8c8b05042c4ee02eacf07

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

4394397manual merge with 6.7.beta2
f219ce3Fixed whitespace errors and corrected second-hand lazy import (probably a merge error)

comment:88 Changed 7 years ago by git

  • Commit changed from f219ce3a60512bac0da8c8b05042c4ee02eacf07 to ebc2a65c5d377cc1e7872201709fabcec3e9e4c6

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

e9bcfdaMerge branch 'public/categories/filtered_algebras-17096' into 6.7.rc0
ebc2a65trac #17096 fixing two doctests

comment:89 Changed 7 years ago by chapoton

see also #15328

comment:90 Changed 7 years ago by vdelecroix

Patchbot is not yet happy (but for very stupid reasons).

comment:91 Changed 7 years ago by git

  • Commit changed from ebc2a65c5d377cc1e7872201709fabcec3e9e4c6 to 4b2046fdfb0545b3b0908f8c3de609becd78bc5f

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

9cf5607Merge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/categories/filtered_algebras-17096
26859cbmanual merge with sage 6.7.beta1
6051865add a doctest which hopefully works (hard to check while compiling)
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

comment:92 Changed 7 years ago by git

  • Commit changed from 4b2046fdfb0545b3b0908f8c3de609becd78bc5f to 3f67b6b0d0e10c2f4816acc791f6dc2a016eeb8d

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

3f67b6bFixing trivial doctest due to changes in category heirarchy.

comment:93 Changed 7 years ago by git

  • Commit changed from 3f67b6b0d0e10c2f4816acc791f6dc2a016eeb8d to fa476ddac910418cb12790af8896154ddca8fd00

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

fa476ddFixing double-colon in INPUT block.

comment:94 Changed 7 years ago by tscrim

  • Milestone changed from sage-6.6 to sage-6.10

comment:95 Changed 7 years ago by darij

  • Reviewers set to Darij Grinberg

comment:96 Changed 7 years ago by git

  • Commit changed from fa476ddac910418cb12790af8896154ddca8fd00 to 589b501685ef7e4d07b159d56b1049a1d1e67759

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

589b501Reviewer changes with Darij.

comment:97 Changed 7 years ago by git

  • Commit changed from 589b501685ef7e4d07b159d56b1049a1d1e67759 to 6cc8b8460dfe5a05380e73e667dc7294e4369774

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

6cc8b84Reviewer changes with Darij.

comment:98 Changed 7 years ago by darij

  • Status changed from needs_review to positive_review

After a harrowing hour of discussing the category framework, I found myself agreeing with this ticket. Thanks Travis for the changes!

comment:99 Changed 7 years ago by vbraun

  • Branch changed from public/categories/filtered_algebras-17096 to 6cc8b8460dfe5a05380e73e667dc7294e4369774
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.