Opened 8 years ago

Closed 8 years ago

# Implement direct sum and tensor products for chain complexes and Koszul complexes

Reported by: Owned by: tscrim tscrim major sage-6.4 algebraic topology jhpalmieri Travis Scrimshaw John Palmieri N/A 2253260 22532605d2973f86ec8f45f2f68f31c1f96481ae

### 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.

### comment:1 Changed 8 years ago by git

• Commit changed from c392d1c6dcd603c925ffdfbc27d26d089f422526 to 01158352cb6751e7286023c3031ad1120fa3cca1

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

 ​e05aa55 `Merge branch 'develop' into u/tscrim/koszul_complexes` ​0115835 `Finalizing for review.`

### comment:2 Changed 8 years ago by tscrim

• Status changed from new to needs_review

### comment:3 follow-up: ↓ 4 Changed 8 years ago by 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 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 0|0 0]
[0 1 0 0|0 0]
[0 0 1 0|0 0]
[0 0 0 1|0 0]
[-------+---]
[0 0 0 0|1 0]
[0 0 0 0|0 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 top-level. Having them at the top-level 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 ; follow-up: ↓ 5 Changed 8 years ago by tscrim

Thanks for taking a look at this!

I will make all of these changes once my Sage rebuilds (probably late tonight or tomorrow).

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`.

Good point. Will do.

I think you can delete the line `zero = R.zero()` in `cartesian_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 0|0 0]
[0 1 0 0|0 0]
[0 0 1 0|0 0]
[0 0 0 1|0 0]
[-------+---]
[0 0 0 0|1 0]
[0 0 0 0|0 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.

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` or `tensor_product`?

The functorial construction is `tensor`, so I have to use that.

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)`.

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 top-level. Having them at the top-level could potentially slow down startup times, I think.

Importing them at the top-level 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 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.

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 ; follow-up: ↓ 6 Changed 8 years ago by jhpalmieri

I think you can delete the line `zero = R.zero()` in `cartesian_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 top-level. Having them at the top-level could potentially slow down startup times, I think.

Importing them at the top-level 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 tscrim

Before it gets used, `zero` is redefined by `zero = matrix(R, [])`, isn't it?

*facepalm*

Importing them at the top-level 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 git

• Commit changed from 01158352cb6751e7286023c3031ad1120fa3cca1 to 990c0dce6e53a005eb2b3cd44709379f5d7bf242

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

 ​58bf48c `Merge branch 'u/tscrim/koszul_complexes' of trac.sagemath.org:sage into u/tscrim/koszul_complexes` ​990c0dc `Fixes from John's comments.`

### comment:8 Changed 8 years ago by tscrim

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 jhpalmieri

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 class ChainComplex_class(Parent): ret = {k: matrix.block_diagonal([d.get(k, zero) for d in diffs], subdivide=subdivide) for k in keys} return ChainComplex(ret, degree_of_differential=deg_diff) return ChainComplex(ret, degree_of_differential=deg_diff, grading_group=self._grading_group) def tensor(self, *factors, **kwds): r"""

You'll need a similar change at the end of the `tensor` method.

### comment:10 Changed 8 years ago by git

• Commit changed from 990c0dce6e53a005eb2b3cd44709379f5d7bf242 to 58b45d9b8aa6366b5d8c54edc320e0ec503b3d93

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

 ​58b45d9 `Added support for general grading groups.`

Fixed3.

### comment:12 Changed 8 years ago by jhpalmieri

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 git

• 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.`

Whoops; fixed.

### comment:15 Changed 8 years ago by jhpalmieri

• 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 tscrim

Thanks for doing the review.

### comment:17 Changed 8 years ago by vbraun

• Branch changed from u/tscrim/koszul_complexes to 22532605d2973f86ec8f45f2f68f31c1f96481ae
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.