Add Commutative graded differential algebras.

miguelmarco commented 10 years ago

This patch adds basic CDGA's.

They work as follows, first you create the algebra:

sage: A.<x,y,t> = CDGAlgebra(QQ, degrees = (1, 1, 2))
sage: A
Graded Commutative Algebra over Rational Field with generators ('x', 'y', 't') in degrees (1, 1, 2)

Then define the differential on A to construct a differential graded algebra:

sage: sage: B = A.CDGAlgebra({x: x*y , y: x*y })
sage: B
Commutative Differential Graded Algebra over Rational Field with generators ('x', 'y', 't') in degrees (1, 1, 2), differential 
    x --> x*y
    y --> x*y
    t --> 0

Now you can compute things like a basis of each homogeneous part:

sage: B.basis(5)
[y*t^2, x*t^2]

Or the cohomology in each degree:

sage: B.cohomology(4)
Free module generated by {[t^2]} over Rational Field
sage: B.cohomology(9)
Free module generated by {[-x*t^4 + y*t^4]} over Rational Field

Depends on #17224

CC: @vbraun @simon-king-jena @saraedum @tscrim

Component: algebra

Keywords: sd58, sd59, algebras, noncommutative, graded

Author: Miguel Marco, John Palmieri

Branch: 3900c66

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/16508

miguelmarco commented 10 years ago

Branch: u/mmarco/ticket/16508

miguelmarco commented 10 years ago

comment:2

One problem there is is that objects don't pickle correctly. This is an inherited problem from elements in g-algebra quotients (which are inherited here).

New commits:

`9e3e986`	`Added CDGA's`
`6a80cf5`	`Minor fix`

miguelmarco commented 10 years ago

Commit: 6a80cf5

simon-king-jena commented 10 years ago

comment:3

Replying to @miguelmarco:

One problem there is is that objects don't pickle correctly. This is an inherited problem from elements in g-algebra quotients (which are inherited here).

I think this should be fixed.

Bike-shedding: You sa "commutative graded differential algebra", which I believe is the correct order of adjectives. But then, the class should be called "CGDAlgebra", not "CDGAlgebra".

jhpalmieri commented 10 years ago

comment:4

Interesting, I've been working on such a class myself. If I push my branch, it will replace the one here. Is there a way to make both branches available at the same time, for comparison?

tscrim commented 10 years ago

comment:5

Just state the name of your branch (and make sure it's been pushed to trac of course).

jhpalmieri commented 10 years ago

comment:6

Okay, it's here: u/jhpalmieri/DGA

jhpalmieri commented 10 years ago

comment:7

I like the fact that the branch here uses QuotientRing_nc, which mine doesn't do. On the other hand, I think that a differential graded algebra should be endowed with a differential: the differential should not be a separate piece of structure.

miguelmarco commented 10 years ago

comment:8

Replying to @simon-king-jena:

Replying to @miguelmarco:

One problem there is is that objects don't pickle correctly. This is an inherited problem from elements in g-algebra quotients (which are inherited here).

I think this should be fixed.

I think it is a matter for another ticket. If it is solved in the g-algebra quotents, it should also solve the issue here.

Bike-shedding: You sa "commutative graded differential algebra", which I believe is the correct order of adjectives. But then, the class should be called "CGDAlgebra", not "CDGAlgebra".

I know it is a mit oa mess, but in the literature they usually appear as CDGA's

miguelmarco commented 10 years ago

comment:9

Replying to @jhpalmieri:

I like the fact that the branch here uses QuotientRing_nc, which mine doesn't do. On the other hand, I think that a differential graded algebra should be endowed with a differential: the differential should not be a separate piece of structure.

I talked with saraedum about that. My original idea was that, but it had some problems:

1) If the differential is to be defined at creation time, we can not use elements of the parent to determine it, so we should give tuples of dictionaries or something like that. Not user friendly at all.

2) If we set the differential after the object creation, the parent is mutable, which is a problem for pickling, unique representation and so on.

So after considering all, i think that this approach is a decent compromise between user friendlyness and immutability

tscrim commented 10 years ago

comment:10

In talking with Miguel, we're thinking that I write the categories (using axioms) that holds the abstract and general/common methods. Then we (you and/or Miguel) have parents for (Free)(Commutative)GradedAlgebra, which we create first and pass to the differential version.

I would like to have these categories for #15300 (Clifford/exterior algebras) anyways, and have opened #16513 for this.

jhpalmieri commented 10 years ago

comment:11

Replying to @miguelmarco:

Replying to @jhpalmieri:

I like the fact that the branch here uses QuotientRing_nc, which mine doesn't do. On the other hand, I think that a differential graded algebra should be endowed with a differential: the differential should not be a separate piece of structure.

I talked with saraedum about that. My original idea was that, but it had some problems:

1) If the differential is to be defined at creation time, we can not use elements of the parent to determine it, so we should give tuples of dictionaries or something like that. Not user friendly at all.

2) If we set the differential after the object creation, the parent is mutable, which is a problem for pickling, unique representation and so on.

So after considering all, i think that this approach is a decent compromise between user friendlyness and immutability

Take a look at how I did it in my branch.

jhpalmieri commented 10 years ago

comment:12

Two more comments: "DGA" and "CDGA" are standard in the literature, but so is "differential graded algebra" (as opposed to "graded differential algebra").

Second, it would be very nice (for possible future implementation of spectral sequences) to allow grading by Z x Z, or indeed any free abelian group.

jhpalmieri commented 10 years ago

comment:13

A question: what about hooking this into the graded commutative algebra class sage.rings.polynomial.plural.SCA?

miguelmarco commented 10 years ago

comment:14

SCA is just a function that returns a certain g_algebra quotient.

We already create that kind of quotient here, but with two advantages:

1) We include the degrees in the definition of the g_algebra 2) We allow quotient by arbitrary relations (not just the squares of the odd generators).

tscrim commented 10 years ago

comment:15

Replying to @jhpalmieri:

A question: what about hooking this into the graded commutative algebra class sage.rings.polynomial.plural.SCA?

As Miguel stated, it's just a function which creates the super commutative algebra. What we'll do is replace that method with our parent and subsume SCA's construction in the __init__ of the parent.

jhpalmieri commented 10 years ago

comment:16

I'm trying to reconcile your comments with what I see in plural.pyx; see also http://www.singular.uni-kl.de/Manual/latest/sing_532.htm. SCA is defined in terms of the class NCPolynomialRing_plural, which uses Singular's nc_algebra function. I don't see any references in quotient_ring.py to plural.pyx or to nc_algebra or related Singular machinery, so the relationship between QuotientRing_nc and SCA is not clear to me.

miguelmarco commented 10 years ago

comment:17

If you look at the code of SCA, it is just a function that:

1. Creates a Free Algebra
1. Creates a dictionary with the commutatitivty/anticommutativity relations
3.Creates the corresponding g-algebra
1. Creates the ideal in the g-algebra generated by the squares of the odd generators
1. returns the quotient of the g-algebra by the ideal

The result of this last operation is an object of type QuoitientRing_nc_with_category, that basically wraps the corresponding plural object.

Look:

sage: from sage.rings.polynomial.plural import SCA
sage: A=SCA(QQ,('x','y','z'),[0,1])
sage: type(A)
<class 'sage.rings.quotient_ring.QuotientRing_nc_with_category'>
sage: A.__module__
'sage.rings.quotient_ring'

QuotientRing_nc has no references to plural because it is created by passing already plural objects (the g-algebra and the ideal in this case), so it relies on the functionality that they provide.

tscrim commented 10 years ago

Changed keywords from sd58, algebras, nonconmutative, graded to sd58, sd59, algebras, nonconmutative, graded

jhpalmieri commented 10 years ago

comment:19

I think I see. It looks like QuotientRing_nc doesn't have anything to do with plural, but it can take plural rings as arguments, which is what happens in your case.

jhpalmieri commented 10 years ago

comment:20

By the way, for both this ticket and #16513, in my branch the method homology_algebra is incomplete. I think that everything else works and has doctests.

tscrim commented 10 years ago

comment:21

BTW, what's in #16513 is (currently) skeletal code and will likely need to be merged simultaneously with this in order to have reasonable doctests (as opposed to just using a toy example, which we should implement in #16513).

tscrim commented 10 years ago

Dependencies: #16513

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

`acf90f3`	`Merge branch 'develop' into ticket/16508`
`ebf50e3`	`Initial setup for differential axiom.`
`4f3d561`	`Merge branch 'ticket/16513' into ticket/16508`
`ff33930`	`Partial rewrite`
`b607648`	`minor change`
`61487e6`	`More polished implementation, storing the differential inside the algebra.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 6a80cf5 to 61487e6

miguelmarco commented 10 years ago

Changed dependencies from #16513 to none

miguelmarco commented 10 years ago

comment:24

I still haven't tried to use the new category. Will try to look at it tomorrow.

In the meantime, you can check this implementation.

jhpalmieri commented 9 years ago

comment:25

Here is a new branch: u/jhpalmieri/DGA_new. (Is there some sort of markup I can give to make that an active link? Should we make it the official branch attached to this ticket?)

This is a complete rewrite based on Miguel's version, and so built on top of QuotientRing_nc. Changes:

I removed all of the category stuff. That can go on a separate ticket (#16513).
I added the option to multi-grade the objects, using commands like

A.<x,y,z> = CDGAlgebra(QQ, degrees=((1,0), (0,1), (2,0)))

Tinkered with documentation. Added the main file to the reference manual.
Various code modifications and clean up. Among other things:
Sped up GCAlgebra.homogeneous_part. The old version was GCAlgebra.homogeneous_part, the new version GCAlgebra.basis. In my current code, there is some caching going on, but when doing these timings, I disabled the caching.

sage: A.<t,x,y,z> = CDGAlgebra(QQ, degrees=(1,1,2,4))
sage: A.homogeneous_part(10)
[y*z^2, t*x*z^2, y^3*z, t*x*y^2*z, y^5, t*x*y^4]
sage: A.basis(10)
[t*x*z^2, t*x*y^2*z, t*x*y^4, y*z^2, y^3*z, y^5]
sage: sorted(A.homogeneous_part(10)) == sorted(A.basis(10))
True
sage: sorted(A.homogeneous_part(40)) == sorted(A.basis(40))
True
sage: timeit('A.homogeneous_part(40)') # original version
5 loops, best of 3: 440 ms per loop
sage: timeit('A.basis(40)')            # new version
25 loops, best of 3: 12.9 ms per loop

Sped up _call_ method for CDGA_Differential:

sage: A.<t,x,y,z> = CDGAlgebra(QQ, degrees=(1,1,2,4))
sage: B = CDGAlgebra(A, differential={t:y, x:y})
sage: a = t*x*y**20*z**20
sage: timeit('B.differential()._call1_(a)')   # original version
25 loops, best of 3: 19.6 ms per loop
sage: timeit('B.differential()._call3_(a)')   # new version
125 loops, best of 3: 2.38 ms per loop

Rewrote is_homogeneous based on other such methods elsewhere in Sage. It's slightly faster this way.
Should it be "commutative graded algebra" or "graded commutative algebra"? I think the second is more standard – for example, the phrase "graded commutativity" is commonly used – and after some thought, that's what I used in the rewrite. ("Commutative graded algebra" sounds like a graded algebra that happens to be commutative, implying strict commutativity. In "graded commutative algebra", "graded" modifies both "commutative" and the algebra, so the algebra is graded and the commutativity has a sign coming from the grading. According to Google search, there are about four times as many hits for "graded commutative algebra" compared to "commutative graded algebra". Similarly for a search on http://mathoverflow.net.)
On the other hand, "differential graded algebra" is completely standard, and so is "commutative differential graded algebra". So the adjectives are not ordered consistently in the different types of algebras.
So the main classes and functions are GCAlgebra and CDGAlgebra. The second of these is the only thing imported at the top-level.

Comments and questions:

GCAlgebra._element_constructor_ works unexpectedly: if B and C are quotients of A, then you can convert elements of B to elements of C. For example:

sage: A.<x,y,z> = CDGAlgebra(QQ, degrees=(1, 2, 1))
sage: B = A.quotient(A.ideal(z))
sage: C = A.quotient(A.ideal(x*y))
sage: C.inject_variables()
Defining x, y, z
sage: x*y
0
sage: B(x*y)
0
sage: B(x)*B(y)
x*y

However, it looks like this is just a slightly modified version of the same method from rings/quotient_ring.py, so maybe we should leave it as is. Maybe that method could use some documentation, though.

When initializing a graded commutative algebra, what should we do if neither names or degrees is specified (as in GCAlgebra(QQ))? Right now I'm raising an error.
TestSuite fails on these algebras:

The following tests failed: _test_elements, _test_pickling

Is that important?

miguelmarco commented 9 years ago

comment:26

Thanks for the work. I will leave on holidays tomorrow, so don't know when i will have time to look at it.

Just a few quick comments:

About the names... it seems to be several choices in the literature. I am ok with any of them.

About the filing tests, as i mentioned before, is a problem that comes inherited from g-algebra quotients. It should be fixed in a different ticket.

About the conversion between different quotients, i think it is ok. It is a conversion, not a coercion, so we can be much less strict. I think it makes sense to convert between parents with the same kind of structure and generators with the same names.

About initializing without names and degrees, i think raising an error is the right thing to do. It is what happens if, for instance, you try to create a polynomial ring without the names of the generators.

tscrim commented 9 years ago

Changed commit from 61487e6 to f5f4c1d

tscrim commented 9 years ago

comment:27

@jhpalmieri Easiest thing is to just change the branch since that is the current (most?) working version. Worst case we just change the branch back.

I'm fine with this not depending on #16513. When I see Nicolas in 2 weeks, we'll work more on the category side of things. Plus if there is an actual implementation, it will make doing the doctesting much easier.

New commits:

f5f4c1d Differential graded algebras

tscrim commented 9 years ago

Changed branch from u/mmarco/ticket/16508 to u/jhpalmieri/DGA_new

jhpalmieri commented 9 years ago

Description changed:

--- 
+++ 
@@ -3,43 +3,34 @@
 They work as follows, first you create the algebra:

-sage: A = CDGAlgebra(QQ, 'x,y,t', degrees = (1, 1, 2)) +sage: A.<x,y,t> = CDGAlgebra(QQ, degrees = (1, 1, 2)) sage: A -Commutative Graded Differential Algebra over Rational Field with generators ('x', 'y', 't') -sage: A.inject_variables() -Defining x, y, t +Graded Commutative Algebra over Rational Field with generators ('x', 'y', 't') in degrees (1, 1, 2)


-Then define the differential:
+Then define the differential on `A` to construct a differential graded algebra:

-sage: D = A.differential({x: xy , y: xy }) -sage: D -Differential map in Commutative Graded Differential Algebra over Rational Field with generators ('x', 'y', 't') -sending: +sage: sage: B = A.CDGAlgebra({x: xy , y: xy }) +sage: B +Commutative Differential Graded Algebra over Rational Field with generators ('x', 'y', 't') in degrees (1, 1, 2), differential x --> xy y --> xy t --> 0


 Now you can compute things like a basis of each homogeneous part:

-sage: A.homogeneous_part(5) +sage: B.basis(5) [yt^2, xt^2]


-Or the cohomology at each degree:
+Or the cohomology in each degree:

-sage: A.cohomology(4, D) -Vector space quotient V/W of dimension 1 over Rational Field where -V: Vector space of degree 2 and dimension 2 over Rational Field -Basis matrix: -[1 0] -[0 1] -W: Vector space of degree 2 and dimension 1 over Rational Field -Basis matrix: -[0 1] +sage: B.cohomology(4) +Free module generated by {[t^2]} over Rational Field +sage: B.cohomology(9) +Free module generated by {[-xt^4 + yt^4]} over Rational Field

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`eecb23e`	`more DGAs`
`e2ae6c0`	`Merge branch 'develop' into DGA`
`0dca97f`	`Merge branch 'develop' into DGA`
`1395216`	`Convert all tuples and lists to vectors before converting to elements`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from f5f4c1d to 1395216

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 1395216 to 1c136cb

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`cc88cee`	`Merge branch 'develop' into t/16508/DGA_new`
`1c136cb`	`Lazily import CDGAlgebra`

jhpalmieri commented 9 years ago

comment:32

Ping...

jhpalmieri commented 9 years ago

comment:33

By the way, I found the branch here very useful in computing some examples related to http://mathoverflow.net/questions/182437/is-homology-finitely-generated-as-an-algebra.

tscrim commented 9 years ago

comment:34

Sorry, I didn't get much of a change to talk with Nicolas about the categories. However this ticket is the next on my to-do list of reviews (once I get done with math stuff).

miguelmarco commented 9 years ago

comment:35

Replying to @jhpalmieri:

By the way, I found the branch here very useful in computing some examples related to http://mathoverflow.net/questions/182437/is-homology-finitely-generated-as-an-algebra.

So i guess that means that we cannot write a method to compute the cohomology algebra of a cdga. Unless there is some algorithm that can compute it in some cases. Or that we somehow implement infinitely generated cdga's.

jhpalmieri commented 9 years ago

comment:36

Replying to @miguelmarco:

So i guess that means that we cannot write a method to compute the cohomology algebra of a cdga.

Possibly in positive characteristic, and in general, we can compute the cohomology algebra through a range of degrees. That might be worthwhile.

tscrim commented 9 years ago

comment:37

Replying to @miguelmarco:

So i guess that means that we cannot write a method to compute the cohomology algebra of a cdga. Unless there is some algorithm that can compute it in some cases. Or that we somehow implement infinitely generated cdga's.

We currently don't have any support for (possibly) infinite (co)chain complexes, but it should be easy enough to implement by doing something like

class InfiniteChainComplex(Parent):
    def __init__(self, grading_group, degree, chain_map, etc):
        # Store all of the necessary input data

    def homology(self, i, R):
        # Return the homology of a finite chain complex that
        #   determines the i-th homology (i.e., truncate ``self``)

Side note - As far as I know, we don't have a way to compute the cup product in Sage (but I haven't looked very hard). I think this would be useful. I also found this on a quick web search: http://www.pawelpilarczyk.com/preprint/2013cubi.pdf.

jhpalmieri commented 9 years ago

comment:38

For cup products, no, we can't do it. I've thought about it on and off, but never enough to do anything about it. See #6102 (and also #6101). I've found some other papers which might be useful. At some point I should add some references to #6102.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 1c136cb to edc8ccd

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`3ecb051`	`Merge branch 'develop' into t/16508/DGA_new`
`edc8ccd`	`Change the top-level function from CDGAlgebra to GradedCommutativeAlgebra.`

jhpalmieri commented 9 years ago

comment:40

After a discussion with Travis, I changed the top-level function from CDGAlgebra to GradedCommutativeAlgebra. Its job is just to create either singly- or multi-graded commutative algebras, creating an instance of the relevant class. Users can then construct commutative DG algebras using the CDGAlgebra method on the graded commutative algebras.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

a4d5b24 Cached methods should return immutable matrices

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from edc8ccd to a4d5b24

tscrim commented 9 years ago

Reviewer: Travis Scrimshaw

sagemath / sage

Add Commutative graded differential algebras. #16508