Opened 8 years ago
Closed 8 years ago
#16851 closed enhancement (fixed)
Implement direct sum and tensor products for chain complexes and Koszul complexes
Reported by:  tscrim  Owned by:  tscrim 

Priority:  major  Milestone:  sage6.4 
Component:  algebraic topology  Keywords:  
Cc:  jhpalmieri  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  John Palmieri 
Report Upstream:  N/A  Work issues:  
Branch:  2253260 (Commits, GitHub, GitLab)  Commit:  22532605d2973f86ec8f45f2f68f31c1f96481ae 
Dependencies:  Stopgaps: 
Description
There is a natural way to construct a chain complex from the direct sum (Cartesian product) and tensor product of chain complexes. This also implements Koszul complexes.
Change History (17)
comment:1 Changed 8 years ago by
 Commit changed from c392d1c6dcd603c925ffdfbc27d26d089f422526 to 01158352cb6751e7286023c3031ad1120fa3cca1
comment:2 Changed 8 years ago by
 Status changed from new to needs_review
comment:3 followup: ↓ 4 Changed 8 years ago by
For cartesian_product
, I think that the requirement that the degrees of the differentials of the factors must agree is completely natural, but it should be mentioned in the docstring and it should probably be doctested. Same for tensor
.
I think you can delete the line zero = R.zero()
in cartesian_product
.
This is odd behavior when subdivide=True
and there is more than one factor:
sage: m = identity_matrix(QQ, 2) sage: C = ChainComplex({0:m}) sage: ascii_art(C.cartesian_product([C,C], subdivide=True)) [1 0 0 00 0] [0 1 0 00 0] [0 0 1 00 0] [0 0 0 10 0] [+] [0 0 0 01 0] [0 0 0 00 1] 0 < C_1 < C_0 < 0
I was expecting the matrix to have subdivisions for each factor, not just the last one. I guess iterating matrix.block_diagonal
doesn't preserve earlier subdivisions as you add more blocks. Something similar happens with tensor
.
Should it be tensor
or tensor_product
?
In cartesian_product
, is it worth pointing out that subdivide
must be specified explicitly? That is, you can't do C.cartesian_product(D, True)
.
In koszul_complex.py
, is the dot intentional in
###################################################.#####################
In that file, people have different styles, but I prefer importing functions only when you need them, not at the toplevel. Having them at the toplevel could potentially slow down startup times, I think.
In the __classcall_private__
method for Koszul complexes, I don't understand the lines
if elements is None: elements = R if not elements: ...
If you call KoszulComplex
with no arguments, you get an error before you reach this stage, so I think the second if
can be skipped. I also gets various unhelpful error messages if I call KoszulComplex(ZZ)
or KoszulComplex(QQ)
without specifying elements
. Maybe if elements
is not specified, set it to an empty tuple instead? That is, if only one argument is passed, if it's an iterable, set R
to be the parent of the first entry. Otherwise, set R
to be that argument and set elements
to be ()
. Or something like that.
I was a little surprised that your code for Koszul complexes didn't use the tensor product you had just defined. I'm guess that your way is faster?
comment:4 in reply to: ↑ 3 ; followup: ↓ 5 Changed 8 years ago by
Thanks for taking a look at this!
I will make all of these changes once my Sage rebuilds (probably late tonight or tomorrow).
Replying to jhpalmieri:
For
cartesian_product
, I think that the requirement that the degrees of the differentials of the factors must agree is completely natural, but it should be mentioned in the docstring and it should probably be doctested. Same fortensor
.
Good point. Will do.
I think you can delete the line
zero = R.zero()
incartesian_product
.
No, it's used when constructing the differentials.
This is odd behavior when
subdivide=True
and there is more than one factor:sage: m = identity_matrix(QQ, 2) sage: C = ChainComplex({0:m}) sage: ascii_art(C.cartesian_product([C,C], subdivide=True)) [1 0 0 00 0] [0 1 0 00 0] [0 0 1 00 0] [0 0 0 10 0] [+] [0 0 0 01 0] [0 0 0 00 1] 0 < C_1 < C_0 < 0I was expecting the matrix to have subdivisions for each factor, not just the last one. I guess iterating
matrix.block_diagonal
doesn't preserve earlier subdivisions as you add more blocks.
I can fix this for the Cartesian product (which I could actually make smarter and faster). Will change.
Something similar happens with
tensor
.
This one I'm not entirely sure I can fix. Would you be okay with just a TODO
comment in the doc about this if I can't fix it?
Should it be
tensor
ortensor_product
?
The functorial construction is tensor
, so I have to use that.
In
cartesian_product
, is it worth pointing out thatsubdivide
must be specified explicitly? That is, you can't doC.cartesian_product(D, True)
.
Since it is part of the explicit arguments (which shows up under ?
), and we expect the user to have a basic knowledge of python syntax, I don't want to put any comments about this.
In
koszul_complex.py
, is the dot intentional in###################################################.#####################
No, that's a typo.
In that file, people have different styles, but I prefer importing functions only when you need them, not at the toplevel. Having them at the toplevel could potentially slow down startup times, I think.
Importing them at the toplevel makes the call to the function faster, which is much more important in this case. However we can lazy import the koszul_complex.py
module, which we should do since I feel that it's not likely too many people will use this.
In the
__classcall_private__
method for Koszul complexes, I don't understand the linesif elements is None: elements = R if not elements: ...If you call
KoszulComplex
with no arguments, you get an error before you reach this stage, so I think the secondif
can be skipped. I also gets various unhelpful error messages if I callKoszulComplex(ZZ)
orKoszulComplex(QQ)
without specifyingelements
. Maybe ifelements
is not specified, set it to an empty tuple instead? That is, if only one argument is passed, if it's an iterable, setR
to be the parent of the first entry. Otherwise, setR
to be that argument and setelements
to be()
. Or something like that.
It was for passing in a list (tuple) of 0 elements. You are right and that I should better handle when passing a base ring with no arguments. Will fix.
I was a little surprised that your code for Koszul complexes didn't use the tensor product you had just defined. I'm guess that your way is faster?
Yes, especially for large number of elements (I don't believe that my code for the tensor product is fast at all and probably could be improved).
comment:5 in reply to: ↑ 4 ; followup: ↓ 6 Changed 8 years ago by
Replying to tscrim:
I think you can delete the line
zero = R.zero()
incartesian_product
.No, it's used when constructing the differentials.
Before it gets used, zero
is redefined by zero = matrix(R, [])
, isn't it?
Something similar happens with
tensor
.This one I'm not entirely sure I can fix. Would you be okay with just a
TODO
comment in the doc about this if I can't fix it?
Sure.
In that file, people have different styles, but I prefer importing functions only when you need them, not at the toplevel. Having them at the toplevel could potentially slow down startup times, I think.
Importing them at the toplevel makes the call to the function faster
Just for the first call, right?
However we can lazy import the
koszul_complex.py
module, which we should do since I feel that it's not likely too many people will use this.
Sounds good.
comment:6 in reply to: ↑ 5 Changed 8 years ago by
Replying to jhpalmieri:
Before it gets used,
zero
is redefined byzero = matrix(R, [])
, isn't it?
*facepalm*
Importing them at the toplevel makes the call to the function faster
Just for the first call, right?
No, every call. If we lazily import them, then its only on the first call. However this is moot because...
However we can lazy import the
koszul_complex.py
module, which we should do since I feel that it's not likely too many people will use this.Sounds good.
...it will only get imported (into the module's scope) when the lazy import gets resolved.
comment:7 Changed 8 years ago by
 Commit changed from 01158352cb6751e7286023c3031ad1120fa3cca1 to 990c0dce6e53a005eb2b3cd44709379f5d7bf242
comment:8 Changed 8 years ago by
Okay, now with a smarter algorithm for cartesian_product
(it is probably faster than before too, but I didn't check), we can now do KoszulComplex()
, KoszulComplex(ZZ)
, KoszulComplex([])
, and KoszulComplex(ZZ, [])
and get the same results (plus KoszulComplex(QQ)
works too), and other fixes based off your comments.
comment:9 Changed 8 years ago by
The tensor product doesn't work if the chain complex is graded over a free abelian group: computing (1)^a
fails in this case, because a
is a group element, not an integer. So you need to test for this case and replace a
with sum(a)
or something similar. (See also the total_degree
function in my branch at #16508.)
A related problem: if the differential has degree d
, then I think the correct formula for the differential on the tensor product x tensor y
involves the sign (1)^(x * d)
, where d
is the degree of the differential on the second factor. With this sign convention (or with your choice of (1)^x
), if C
and D
are chain complexes with differentials of even degree, their tensor product will probably not be a chain complex any more, because the differential won't square to zero. It would be a good idea to add a warning about this in the documentation. (I know why you might want to grade over an arbitrary free abelian group, but I don't know why you would want a differential of even degree, so this is probably not a big deal.)
Oh, and cartesian_product
fails if graded over something other than ZZ
, because the grading group needs to be explicitly stated if it's not ZZ
. So something like this should fix it:

src/sage/homology/chain_complex.py
diff git a/src/sage/homology/chain_complex.py b/src/sage/homology/chain_complex.py index 1c6fdfb..29ce6e7 100644
a b class ChainComplex_class(Parent): 1758 1758 ret = {k: matrix.block_diagonal([d.get(k, zero) for d in diffs], 1759 1759 subdivide=subdivide) 1760 1760 for k in keys} 1761 return ChainComplex(ret, degree_of_differential=deg_diff) 1761 return ChainComplex(ret, degree_of_differential=deg_diff, 1762 grading_group=self._grading_group) 1762 1763 1763 1764 def tensor(self, *factors, **kwds): 1764 1765 r"""
You'll need a similar change at the end of the tensor
method.
comment:10 Changed 8 years ago by
 Commit changed from 990c0dce6e53a005eb2b3cd44709379f5d7bf242 to 58b45d9b8aa6366b5d8c54edc320e0ec503b3d93
Branch pushed to git repo; I updated commit sha1. New commits:
58b45d9  Added support for general grading groups.

comment:11 Changed 8 years ago by
Fixed^{3}.
comment:12 Changed 8 years ago by
It looks like the sign in the tensor product doesn't involve the degree of the differential. Otherwise, everything looks okay.
comment:13 Changed 8 years ago by
 Commit changed from 58b45d9b8aa6366b5d8c54edc320e0ec503b3d93 to 22532605d2973f86ec8f45f2f68f31c1f96481ae
Branch pushed to git repo; I updated commit sha1. New commits:
2253260  Added the diff degree to the scalar computation.

comment:14 Changed 8 years ago by
Whoops; fixed.
comment:15 Changed 8 years ago by
 Reviewers set to John Palmieri
 Status changed from needs_review to positive_review
Okay, I'm happy with this now.
comment:16 Changed 8 years ago by
Thanks for doing the review.
comment:17 Changed 8 years ago by
 Branch changed from u/tscrim/koszul_complexes to 22532605d2973f86ec8f45f2f68f31c1f96481ae
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Merge branch 'develop' into u/tscrim/koszul_complexes
Finalizing for review.