Opened 11 years ago

Closed 4 years ago

#6101 closed enhancement (fixed)

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

Reported by: bantieau Owned by: bantieau
Priority: major Milestone: sage-6.10
Component: algebraic topology Keywords:
Cc: jhpalmieri, nthiery, SimonKing Merged in:
Authors: John Palmieri Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: e9150ca (Commits) Commit: e9150caff3d157cadd739042461d972c9d5952f1
Dependencies: #19179, #6102, #18175 Stopgaps:

Description (last modified by jhpalmieri)

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 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:5 Changed 4 years ago by jhpalmieri

  • Dependencies set to #19179
  • Report Upstream set to N/A

comment:6 Changed 4 years ago by jhpalmieri

  • Dependencies changed from #19179 to #19179, #6102

comment:7 Changed 4 years ago by jhpalmieri

  • Branch set to u/jhpalmieri/induced-maps

comment:8 Changed 4 years ago by jhpalmieri

  • Commit set to 698ba79f9837c3c2e83bd358441b4cd4a4073392
  • Status changed from new to needs_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 4 years ago by jhpalmieri

  • Priority changed from minor to major

comment:10 Changed 4 years ago by cnassau

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 follow-up: Changed 4 years ago by chapoton

doc does not build

WARNING: citation not found: G-DR

comment:12 in reply to: ↑ 11 Changed 4 years ago by jhpalmieri

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 4 years ago by tscrim

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 4 years ago by git

  • Commit changed from 698ba79f9837c3c2e83bd358441b4cd4a4073392 to b925f7c8f3b82027ae18e05f0bd93e0e9969ae04

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

b925f7ctrac 6101: add domain and codomain methods.

comment:15 follow-up: Changed 4 years ago by 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).

comment:16 Changed 4 years ago by git

  • Commit changed from b925f7c8f3b82027ae18e05f0bd93e0e9969ae04 to 36a0db648c8fc4c5e0c0ef35059dd13ad6ba0575

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 follow-up: Changed 4 years ago by jhpalmieri

  • Description modified (diff)

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

comment:18 Changed 4 years ago by git

  • Commit changed from 36a0db648c8fc4c5e0c0ef35059dd13ad6ba0575 to 048061cb41ace2fb9563cf99bb2f7f9fcbe80516

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 4 years ago by cnassau

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 4 years ago by jhpalmieri

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 4 years ago by cnassau

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 4 years ago by git

  • Commit changed from 048061cb41ace2fb9563cf99bb2f7f9fcbe80516 to 470ca9b742e1efc2159b004f1b4edd9fd038eea9

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 4 years ago by git

  • Commit changed from 470ca9b742e1efc2159b004f1b4edd9fd038eea9 to 6e3e801ccb73a6dca8c5e4bd05da0e87a511d437

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 4 years ago by tscrim

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

comment:25 follow-up: Changed 4 years ago by jhpalmieri

  • Status changed from needs_review to needs_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 4 years ago by tscrim

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 4 years ago by git

  • Commit changed from 6e3e801ccb73a6dca8c5e4bd05da0e87a511d437 to ec81de20addced6a723f51413c3ffb31eaf4bc13

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 4 years ago by jhpalmieri

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 4 years ago by tscrim

  • Milestone changed from sage-6.4 to sage-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 4 years ago by jhpalmieri

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 4 years ago by tscrim

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 4 years ago by jhpalmieri

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 4 years ago by tscrim

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 4 years ago by git

  • Commit changed from ec81de20addced6a723f51413c3ffb31eaf4bc13 to 953e0a6489a3eca48b13b1e91ece798c51a6fe5c

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 4 years ago by jhpalmieri

  • Dependencies changed from #19179, #6102 to #19179, #6102, #18175
  • Status changed from needs_work to needs_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 4 years ago by jhpalmieri

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

comment:37 Changed 4 years ago by tscrim

I will work on this later this week.

comment:38 Changed 4 years ago by tscrim

  • Authors set to John Palmieri
  • Branch changed from u/jhpalmieri/induced-maps to public/algtop/induced_maps-6101
  • Cc nthiery SimonKing added
  • Commit changed from 953e0a6489a3eca48b13b1e91ece798c51a6fe5c to b6c565763a2df99471bb6b574f60d15450b44c2e
  • Reviewers set to 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 4 years ago by git

  • Commit changed from b6c565763a2df99471bb6b574f60d15450b44c2e to e9150caff3d157cadd739042461d972c9d5952f1

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

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

comment:40 Changed 4 years ago by tscrim

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 4 years ago by jhpalmieri

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

comment:42 Changed 4 years ago by tscrim

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 4 years ago by jhpalmieri

  • Status changed from needs_review to positive_review

comment:44 Changed 4 years ago by vbraun

  • Branch changed from public/algtop/induced_maps-6101 to e9150caff3d157cadd739042461d972c9d5952f1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.