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: sage-6.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:

Status badges

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 git

  • Commit changed from c392d1c6dcd603c925ffdfbc27d26d089f422526 to 01158352cb6751e7286023c3031ad1120fa3cca1

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

e05aa55Merge branch 'develop' into u/tscrim/koszul_complexes
0115835Finalizing for review.

comment:2 Changed 8 years ago by tscrim

  • Status changed from new to needs_review

comment:3 follow-up: 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: 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).

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 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: Changed 8 years ago by jhpalmieri

Replying to tscrim:

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

Replying to jhpalmieri:

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:

58bf48cMerge branch 'u/tscrim/koszul_complexes' of trac.sagemath.org:sage into u/tscrim/koszul_complexes
990c0dcFixes 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 b class ChainComplex_class(Parent): 
    17581758        ret = {k: matrix.block_diagonal([d.get(k, zero) for d in diffs],
    17591759                                         subdivide=subdivide)
    17601760               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)
    17621763
    17631764    def tensor(self, *factors, **kwds):
    17641765        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:

58b45d9Added support for general grading groups.

comment:11 Changed 8 years ago by tscrim

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:

2253260Added the diff degree to the scalar computation.

comment:14 Changed 8 years ago by tscrim

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.