Opened 14 years ago

Closed 7 years ago

#6101 closed enhancement (fixed)

computation of induced morphism on homology and cohomology of simplicial complex morphisms

Reported by: Ben Antieau Owned by: Ben Antieau
Priority: major Milestone: sage-6.10
Component: algebraic topology Keywords:
Cc: John Palmieri, Nicolas M. Thiéry, Simon King Merged in:
Authors: John Palmieri Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: e9150ca (Commits, GitHub, GitLab) Commit: e9150caff3d157cadd739042461d972c9d5952f1
Dependencies: #19179, #6102, #18175 Stopgaps:

Status badges

Description (last modified by John Palmieri)

Add functionality to sage to compute the effect of a simplicial complex morphism on homology and cohomology.

This patch will rely on fuctionality in #6099, #6100, #6102, and #5882.

Change History (44)

comment:1 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:2 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:3 Changed 9 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:4 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:5 Changed 7 years ago by John Palmieri

Dependencies: #19179
Report Upstream: N/A

comment:6 Changed 7 years ago by John Palmieri

Dependencies: #19179#19179, #6102

comment:7 Changed 7 years ago by John Palmieri

Branch: u/jhpalmieri/induced-maps

comment:8 Changed 7 years ago by John Palmieri

Commit: 698ba79f9837c3c2e83bd358441b4cd4a4073392
Status: newneeds_review

New commits:

dece275trac 19179: chain homotopies, chain contractions, and duals of chain maps
763a8a8trac 6102: cup products, cohomology rings, mod 2 cohomology operations
d7b9ed4change AssertionError to other errors
d63774bMerge branch 'chains' into AT-model
c0918b8change AttributeErrors to other errors
698ba79trac 6101: maps in (co)homology induced by simplicial maps

comment:9 Changed 7 years ago by John Palmieri

Priority: minormajor

comment:10 Changed 7 years ago by Christian Nassau

Hi John,

This seems pretty interesting. I just started to play around with it and was struck by a couple of minor usability issues:

sage: X=simplicial_complexes.BrucknerGrunbaumSphere()
sage: phi, M = algebraic_topological_model(X, GF(2))
sage: phi
Chain homotopy between Chain complex morphism from Chain complex with at most 4 nonzero terms over Finite Field of size 2 to Chain complex with at most 4 nonzero terms over Finite Field of size 2 and Chain complex morphism from Chain complex with at most 4 nonzero terms over Finite Field of size 2 to Chain complex with at most 4 nonzero terms over Finite Field of size 2
sage: phi._codomain()
Trivial chain
sage: phi._domain()
Trivial chain
sage: phi._codomain() is phi._domain()
False

As you can see, I made the basic mistake of thinking of "phi._domain" as private functions, when they are in fact just attributes:

sage: phi._domain
Chain complex with at most 4 nonzero terms over Finite Field of size 2
sage: phi._domain is phi._f._domain
True

The Sage maps that I'm used to (mainly morphisms between CombinatorialFreeModules?) have public "domain" and "codomain" methods; this might have spared me a 5 minute detour in this case. I have no good idea, though, what to call the $H_0$ and $H_1$ of a homotopy $H_t$...

Also, I wonder if phi shouldn't better be printed like

sage: phi
Chain homotopy between 
    Chain complex morphism 
      From: Chain complex with at most 4 nonzero terms over Finite Field of size 2
      To:   Chain complex with at most 4 nonzero terms over Finite Field of size 2
and Chain complex morphism
      From: Chain complex with at most 4 nonzero terms over Finite Field of size 2
      To:   Chain complex with at most 4 nonzero terms over Finite Field of size 2

At least this is the way morphisms between combinatorial free modules are printed:

sage: A,B=[CombinatorialFreeModule(GF(2),x) for x in [(1,2,3),(2,3,4)]]
sage: f=A.module_morphism(codomain=B,on_basis = lambda x:x+1) ; f
Generic morphism:
  From: Free module generated by {1, 2, 3} over Finite Field of size 2
  To:   Free module generated by {2, 3, 4} over Finite Field of size 2

comment:11 Changed 7 years ago by Frédéric Chapoton

doc does not build

WARNING: citation not found: G-DR

comment:12 in reply to:  11 Changed 7 years ago by John Palmieri

Replying to chapoton:

doc does not build

WARNING: citation not found: G-DR

Sorry, that should be G-DR03. I'll fix it.

comment:13 Changed 7 years ago by Travis Scrimshaw

As Christian implied, you should use .domain() and .codomain() in the docstring and try to make thing behave like other morphisms as much as possible (anything inheriting from Morphism has some method like _repr_defn or similar).

For the record, this is on my todo list, but I don't know when I might be able to do a full review.

comment:14 Changed 7 years ago by git

Commit: 698ba79f9837c3c2e83bd358441b4cd4a4073392b925f7c8f3b82027ae18e05f0bd93e0e9969ae04

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

b925f7ctrac 6101: add domain and codomain methods.

comment:15 Changed 7 years ago by John Palmieri

Good suggestions, Christian. I've made some changes to try to address them.

Regarding $H_0$ and $H_1$ (currently ._f and ._g), I don't know good names either, but I also almost never needed to use those attributes (only when constructing the dual chain homotopy).

comment:16 Changed 7 years ago by git

Commit: b925f7c8f3b82027ae18e05f0bd93e0e9969ae0436a0db648c8fc4c5e0c0ef35059dd13ad6ba0575

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

d65ba8dtrac 19179: change _repr_ for chain maps, chain homotopies
c38751bMerge branch 'chains' into AT-model
f70e3a2trac 19179: doctest fixes for _repr_ changes
92b17e8Merge branch 'chains' into AT-model
6cd5b7ctrac 6102: doctest fixes for _repr_ changes
36a0db6whitespace fix

comment:17 Changed 7 years ago by John Palmieri

Description: modified (diff)

(Same commits as before, but I also put them on #19179 and #6102, where they really belong.)

comment:18 Changed 7 years ago by git

Commit: 36a0db648c8fc4c5e0c0ef35059dd13ad6ba0575048061cb41ace2fb9563cf99bb2f7f9fcbe80516

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

048061ctrac 6101: add homology_morphism to ref manual

comment:19 in reply to:  17 Changed 7 years ago by Christian Nassau

Replying to jhpalmieri:

(Same commits as before, but I also put them on #19179 and #6102, where they really belong.)

I'm a bit confused by these dependencies - what's the right place to start reviewing things: 6101, 6102, or 19179 ?

comment:20 Changed 7 years ago by John Palmieri

In principle, #19179 is first, then #6102, then this one. However, #19179 has one or two doctests that use things that aren't introduced until #6102, so they will fail. You can read the code there and run everything, though.

#6102 should build and pass doctests, so it would come next (or jointly with #19179). This ticket comes last. The new code for this ticket should be all in the commit labeled "trac 6101: maps in (co)homology induced by simplicial maps".

I suppose I should change the _repr_ method for induced homology maps here, but not right now.

comment:21 in reply to:  15 Changed 7 years ago by Christian Nassau

Replying to jhpalmieri:

Good suggestions, Christian. I've made some changes to try to address them.

Regarding $H_0$ and $H_1$ (currently ._f and ._g), I don't know good names either, but I also almost never needed to use those attributes (only when constructing the dual chain homotopy).

I wonder if we might use bracket-notation, so that a homotopy H goes from H[0] to H[1]? But I don't know if there are precedents in Sage for custom __getitem__, __setitem__ methods. And I'm also not sure, whether there's a real need for this...

comment:22 Changed 7 years ago by git

Commit: 048061cb41ace2fb9563cf99bb2f7f9fcbe80516470ca9b742e1efc2159b004f1b4edd9fd038eea9

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

4e50776trac 19179: hashing of chain maps, chain homotopies
869636bMerge branch 'chains' into AT-model
470ca9btrac 6102: Merge branch 'AT-model' into t/6101/induced-maps

comment:23 Changed 7 years ago by git

Commit: 470ca9b742e1efc2159b004f1b4edd9fd038eea96e3e801ccb73a6dca8c5e4bd05da0e87a511d437

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

07c9c42trac 19179: delete extra line
5923e23trac 6102: Merge branch 'chains' into AT-model
6e3e801trac 6101: Merge branch 'AT-model' into t/6101/induced-maps

comment:24 Changed 7 years ago by Travis Scrimshaw

Okay, last up is this ticket. A first question from a quick lookover is could we use Morphism as the base class?

comment:25 Changed 7 years ago by John Palmieri

Status: needs_reviewneeds_work

This needs to be rebased on top of the most recent #6102. I'm working on it. I'll also look into using Morphism. Does that mean that we also change the already-existing ChainComplexMorphism and SimplicialComplexMorphism?

comment:26 in reply to:  25 Changed 7 years ago by Travis Scrimshaw

Replying to jhpalmieri:

I'll also look into using Morphism. Does that mean that we also change the already-existing ChainComplexMorphism and SimplicialComplexMorphism?

It gives us a little bit of extra features (like register_as_coercion()) and more consistent class hierarchy, but it isn't a requirement. It might also make things easier once homsets become proper parents too, but that is so far down the road that it's not worth it the worry either.

comment:27 Changed 7 years ago by git

Commit: 6e3e801ccb73a6dca8c5e4bd05da0e87a511d437ec81de20addced6a723f51413c3ffb31eaf4bc13

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

0d2ea83trac 6102:
a0f20c2Merge branch 'u/jhpalmieri/AT-model' of trac.sagemath.org:sage into u/jhpalmieri/AT-model
716469aSome smaller reviewer tweaks.
d00d31btrac 6102: cup products for Delta complexes
12d4cc7trac 6102: fix typo "left" -> "right"
8b59ed3Making (co)homology into a graded module (algebra).
3751753Making Sq work for inhomogeneous elements.
9bfc2d2trac 6102: documentation, minor cleanup
8e761deMerge branch 't/6102/AT-model' into t/6101/induced-maps
ec81de2trac 6101: make morphisms inherit from 'Morphism'

comment:28 Changed 7 years ago by John Palmieri

Okay, here's an attempt at using Morphism. I also used Parent for SimplicialComplex (instead of CategoryObject). The only issue with this is that the test suite for simplicial complexes fails unless I skip _test_category.

comment:29 Changed 7 years ago by Travis Scrimshaw

Milestone: sage-6.4sage-6.10

Would you be opposed to basing this on #18175 (which should be positively reviewed soon I hope)? This might solve the issues with _test_category, but I suspect this is more due to a lack of an element class. If you were to use the category of (abstract) simplical complexes from #18175, the intent was that elements correspond to faces.

I should also ask how you feel about using morphism, does it feel any more natural to do things this way or do you think that continuing to work on this isn't worth the time (at this stage)?

comment:30 Changed 7 years ago by John Palmieri

If I try to merge #18175, the test suite fails more tests than before:

The following tests failed: _test_an_element, _test_elements, _test_elements_eq_reflexive, _test_elements_eq_symmetric, _test_elements_eq_transitive, _test_elements_neq, _test_some_elements

because

NotImplementedError: please implement _an_element_ for Simplicial complex ...

I'm not sure what _an_element_ should return: a simplex (since a simplicial complex is a set of simplices)? a vertex (since their images determine maps)? a facet (since they determine the complex)?

As far as morphisms go, it was not hard to switch to them (assuming I did everything right).

comment:31 Changed 7 years ago by Travis Scrimshaw

I would just have it return the first facet (and the empty simplex for the empty complex), but it just has to be any element of the parent object (which could include the empty simplex).

comment:32 Changed 7 years ago by John Palmieri

Going this route tempts me to make Simplex inherit from Element, but you might want to construct abstract instances of Simplex which are not elements of any particular complex. So I can't use the Element.__init__ method, which requires setting a parent. As a result, I don't think I can use _element_constructor_ for simplicial complexes. Instead, I can do something like this (plus doctests):

  • src/sage/homology/simplicial_complex.py

    diff --git a/src/sage/homology/simplicial_complex.py b/src/sage/homology/simplicial_complex.py
    index 8d00cd6..366c1db 100644
    a b class SimplicialComplex(Parent, GenericCellComplex): 
    10771077        """
    10781078        return self._vertex_set
    10791079
     1080    def _an_element_(self):
     1081        return self.facets()[0]
     1082
     1083    def __contains__(self, x):
     1084        if not isinstance(x, Simplex):
     1085            return False
     1086        dim = x.dimension()
     1087        return x in self.n_faces(dim)
     1088
     1089    def __call__(self, simplex):    # not _element_constructor_
     1090        if simplex not in self:
     1091            raise ValueError
     1092        return simplex
     1093
    10801094    def maximal_faces(self):
    10811095        """
    10821096        The maximal faces (a.k.a. facets) of this simplicial complex.

Then the full test suite passes.

comment:33 Changed 7 years ago by Travis Scrimshaw

We can always subclass Simplex as something like SimplexElement and changing out some calls to Simplex(data) to self.element_class(self, data). I wouldn't really want to overwrite __call__ unless we really have to... I can also do some of the work for this changeover as well.

comment:34 Changed 7 years ago by git

Commit: ec81de20addced6a723f51413c3ffb31eaf4bc13953e0a6489a3eca48b13b1e91ece798c51a6fe5c

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

3647305Some cleanup and adding more category information to particular sets.
f810aa6Reworking the category of manifolds.
375ff46Fixing doctest failures and letting a few other rings know they are metric spaces.
8b851a0Merge branch 'develop' into public/categories/topological_metric_spaces-18175
f8f5b93Fixing last remaining doctests.
041a5d1Adding p-adics to metric spaces and some cleanup.
bfa0cdfOne last doc tweak.
d13c368Fixing doc of metric spaces.
9d38c71trac 6101: Merge branch 't/18175/public/categories/topological_metric_spaces-18175' into t/6101/induced-maps
953e0a6trac 6101: add _an_element_, etc., to SimplicialComplex

comment:35 Changed 7 years ago by John Palmieri

Dependencies: #19179, #6102#19179, #6102, #18175
Status: needs_workneeds_review

I tried implementing SimplexElement and it turned into a real mess, so I gave up. Instead, here is my version using __call__.

comment:36 Changed 7 years ago by John Palmieri

Oh, and I would welcome any help with this or other approaches.

comment:37 Changed 7 years ago by Travis Scrimshaw

I will work on this later this week.

comment:38 Changed 7 years ago by Travis Scrimshaw

Authors: John Palmieri
Branch: u/jhpalmieri/induced-mapspublic/algtop/induced_maps-6101
Cc: Nicolas M. Thiéry Simon King added
Commit: 953e0a6489a3eca48b13b1e91ece798c51a6fe5cb6c565763a2df99471bb6b574f60d15450b44c2e
Reviewers: Travis Scrimshaw

Man...non hashable parents really throw a big wrench into the coercion framework. In some ways that is not surprising, as they get put into a big dict to store the necessary coercions, but I would have liked it to better handle non-hashable parents.

Well, one of the problems that you had was Element tries to use coercion on elements which do not define rich comparisons, which caused problems until I changed Simplex.__cmp__ to rich comparisons (I <3 functools.total_ordering). However, even with that change, I could not get the combination of class Element(Simplex, Element) in SimplicialComplex to pickle (granted, I did not try too hard). I think the problem is that SimplicialComplex is defined by a set of its elements, and we get a loop of sorts with the pickling...

Therefore I decided to just add a warning message to SimplicialComplex instead. Simon, Nicolas, the reason I am cc-ing you is to make sure that this abuse of Parent is acceptable to you (or if you had any thoughts about the pickling issues). At least until a follow-up ticket takes care of things.


New commits:

b6c5657Add a warning about the abuse of Parent in simplicial complex.

comment:39 Changed 7 years ago by git

Commit: b6c565763a2df99471bb6b574f60d15450b44c2ee9150caff3d157cadd739042461d972c9d5952f1

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

e9150caMerge branch 'develop' into public/algtop/induced_maps-6101

comment:40 Changed 7 years ago by Travis Scrimshaw

John, if nobody objects to the current setup in a few days, then I think we should set this to positive review.

comment:41 Changed 7 years ago by John Palmieri

Sounds great. I certainly don't have any objection to your warning.

comment:42 Changed 7 years ago by Travis Scrimshaw

Okay, I think we've let enough time for a response pass. Feel free to set a positive review if you're still in agreement.

comment:43 Changed 7 years ago by John Palmieri

Status: needs_reviewpositive_review

comment:44 Changed 7 years ago by Volker Braun

Branch: public/algtop/induced_maps-6101e9150caff3d157cadd739042461d972c9d5952f1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.