Opened 7 weeks ago

Last modified 7 days ago

#31748 needs_review enhancement

PolyhedralComplex

Reported by: yzh Owned by:
Priority: major Milestone: sage-9.4
Component: geometry Keywords: polyhedral complex
Cc: mkoeppe, jhpalmieri, jipilab, tscrim Merged in:
Authors: Yuan Zhou Reviewers:
Report Upstream: N/A Work issues:
Branch: u/yzh/polyhedralcomplex (Commits, GitHub, GitLab) Commit: f5be3fa7f178d9ab0390374781f8f16ca1b86b39
Dependencies: Stopgaps:

Status badges

Description (last modified by mkoeppe)

Create (geometric) PolyhedralComplex, whose cells are Sage Polyhedra.

Change History (44)

comment:1 Changed 7 weeks ago by yzh

  • Branch set to u/yzh/polyhedralcomplex

comment:2 Changed 7 weeks ago by mkoeppe

  • Cc jhpalmieri added
  • Commit set to f76287b8ec12aa28e413a9629b36db20b1e92f2f
  • Description modified (diff)

New commits:

f76287binitial implementation of polyhedral_complex.py

comment:3 Changed 7 weeks ago by git

  • Commit changed from f76287b8ec12aa28e413a9629b36db20b1e92f2f to 577456a0c3ffddef49d02301c4b59a73a7acd636

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

577456amake tox happy

comment:4 Changed 7 weeks ago by git

  • Commit changed from 577456a0c3ffddef49d02301c4b59a73a7acd636 to 38aaf756f91cf3a7e652e9dfdcc0696a1c632afd

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

38aaf75add doc for html build

comment:5 Changed 7 weeks ago by yzh

  • Status changed from new to needs_review

comment:6 Changed 7 weeks ago by mkoeppe

add author name so that the patchbot runs

comment:7 Changed 7 weeks ago by git

  • Commit changed from 38aaf756f91cf3a7e652e9dfdcc0696a1c632afd to 22c902432730cd46535698aa7e8cd2652b6322c4

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

22c9024new methods product, disjoint_union, join

comment:8 Changed 7 weeks ago by yzh

  • Authors set to Yuan Zhou

comment:9 Changed 6 weeks ago by git

  • Commit changed from 22c902432730cd46535698aa7e8cd2652b6322c4 to 0bd40423ef06c9c62dc227eb0f756a0d0290e535

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

add1ec2change _repr_ to show only maximal cells
614dd2drename maximal_cells_list to maximal_cells_sorted, and rename cells_list to cells_sorted
0bd4042is_immutable default is False, set_immutable()

comment:10 Changed 6 weeks ago by git

  • Commit changed from 0bd40423ef06c9c62dc227eb0f756a0d0290e535 to 18c1a33531445265b88c2b1bcd517165d16463d1

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

3cc98f5improve _repr_, factor out cells_list_to_cells_dict
18c1a33def add_cell

comment:11 Changed 6 weeks ago by git

  • Commit changed from 18c1a33531445265b88c2b1bcd517165d16463d1 to 45f080c775da363fa7bb729305a6094b3e32c9d9

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

45f080cimplement PolyhedralComplex.remove_cell()

comment:12 follow-up: Changed 6 weeks ago by yzh

Ready for review.

I don't have much experience with abstract complexes. I'd like to know if this is going in the right direction with Sage homology.

I'm also wondering what other methods of PolyhedralComplex could be interesting. Maybe interactions between PolyhedralComplex and SimplicialComplex such as PolyhedralComplex.subdivide() and SimplicialComplex.geometric_realization()? And interactions between PolyhedralComplex and rational polyhedral fan?

Note that the methods wedge, chain_complex and alexander_whitney are currently missing, as I don't know how to implement them.

Any advice or comment is greatly appreciated! Thanks.

comment:13 Changed 6 weeks ago by yzh

  • Cc jipilab tscrim added

comment:14 Changed 5 weeks ago by git

  • Commit changed from 45f080c775da363fa7bb729305a6094b3e32c9d9 to dfe5cb8e57280ad49f1c4febf898dbbdceba0c4e

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

33be3abimplement subdivide, is_simplicial_complex, is_polyhedral_fan, is_simplicial_fan; allow 3d plot
dfe5cb8make backend optional argument to PolyhedralComplex

comment:15 Changed 5 weeks ago by git

  • Commit changed from dfe5cb8e57280ad49f1c4febf898dbbdceba0c4e to 752011fc6cb7e1ad97b6c4c675e3ba0533df3a91

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

752011fzero is followed by plural countable nouns

comment:16 in reply to: ↑ 12 ; follow-ups: Changed 3 weeks ago by jhpalmieri

Replying to yzh:

Ready for review.

I don't have much experience with abstract complexes. I'd like to know if this is going in the right direction with Sage homology.

It looks good to me so far, thank you for all of the work you've done.

Note that the methods wedge, chain_complex and alexander_whitney are currently missing, as I don't know how to implement them.

I don't know anything about polyhedral complexes. The wedge is the one-point union, and to construct this, you're going to have to translate the two complexes so that they share a point. Is that acceptable? I could imagine taking a complex which has a point (x_1, x_2) and another complex which has a point (y_1, y_2), and forming the join by embedding both in a larger ambient space so that (x_1, x_2) -> (x_1, x_2, y_1, y_2) <- (y_1, y_2) — the first complex lies in the first coordinates, the second in the last coordinates. I don't know if that's a sensible construction from the point of view of people who actually work with these objects.

chain_complex — is there a standard way to produce a chain complex from a polyhedral complex? I would hope so, and I would hope that it's written down somewhere. We shouldn't invent something from scratch. Can we have a method that triangulates the complex and produces a simplicial complex? How hard would that be? I found this: https://sites.millersville.edu/rumble/slides/Seville-Feb-2018.pdf. Is it helpful?

alexander_whitney — I don't know how to handle this (although maybe the Umble slides describe it), and in any case, it's tied to a map of chain complexes, so there is no need to worry about it until the chain complex situation is resolved.

comment:17 Changed 3 weeks ago by jhpalmieri

By the way, is it possible to have a class of abstract polyhedral complexes, in addition to these more concrete complexes? Maybe it would be nice to view the product of two simplicial complexes as an "abstract" polyhedral complex without having to choose embeddings of the simplicial complexes.

comment:18 Changed 3 weeks ago by mkoeppe

That would be #31842 - CombinatorialPolyhedralComplex

comment:19 follow-up: Changed 3 weeks ago by mkoeppe

I am also wondering where delta complexes fit in this story. Is every abstract polyhedral complex a delta complex?

comment:20 in reply to: ↑ 16 ; follow-up: Changed 3 weeks ago by tscrim

Replying to jhpalmieri:

chain_complex — is there a standard way to produce a chain complex from a polyhedral complex? I would hope so, and I would hope that it's written down somewhere. We shouldn't invent something from scratch. Can we have a method that triangulates the complex and produces a simplicial complex? How hard would that be? I found this: https://sites.millersville.edu/rumble/slides/Seville-Feb-2018.pdf. Is it helpful?

My quick thought for the case of a *polytope* complex this is you could take any simplicial complex equivalent to the top-dimensional polytopes to get an equivalent simplicial complex. Then the generalized Stokes theorem would allow you to compute a differential via that simplicial decomposition. Moreover, we should be able to do this with a combinatorial description (i.e., just using the vertices of the polytope complex).

For a polyhedral complex, then we have issues with noncompactness to address. Although in the notes John linked to, they define a polyhedral complex to be with polytope faces. So I think we should be slightly careful about naming to distinguish which objects we allow.

There's a wikipedia stub page about this as well: https://en.wikipedia.org/wiki/Polyhedral_complex The ability to plot tropical varieties would be great to have. (Reminder to myself, I still need to implement tropical polynomials...) It might be good to also link this to special cases such as fans.

comment:21 in reply to: ↑ 16 Changed 3 weeks ago by yzh

@tscrim @jhpalmieri Thank you very much for the feedback! I have yet to study those references.

Replying to jhpalmieri:

Can we have a method that triangulates the complex and produces a simplicial complex?

Do you mean the method PolyhedralComplex.subdivide(make_simplicial=True)? It produces a geometric simplicial complex. Then, #31842 - CombinatorialPolyhedralComplex will take care of making it abstract.

Last edited 3 weeks ago by yzh (previous) (diff)

comment:22 in reply to: ↑ 20 Changed 3 weeks ago by yzh

Replying to tscrim:

It might be good to also link this to special cases such as fans.

I considered to link between PolyhedralComplex and RationalPolyhedralFan. However, I really didn't want to restrict to the rational case only.

comment:23 in reply to: ↑ 19 Changed 3 weeks ago by jhpalmieri

Replying to mkoeppe:

I am also wondering where delta complexes fit in this story. Is every abstract polyhedral complex a delta complex?

The cells in a Delta-complex are all simplices, but maybe any triangulation of an abstract polyhedral complex will always be a Delta-complex. The boundary of a simplex in a Delta-complex is not determined by its vertices: you can make a Delta-complex model of a 2-sphere out of two triangles with a common boundary. Is that allowed in an abstract polyhedral complex?

comment:24 Changed 2 weeks ago by jhpalmieri

In my opinion, we can merge this and then refine later. What do others think?

comment:25 follow-up: Changed 2 weeks ago by mkoeppe

No objection here. It looks great to me!

Minor comment: Shouldn't disjoint_union raise an error if the input is not disjoint?

Typos: interoir->interior, complexe->complex

comment:26 in reply to: ↑ 25 Changed 2 weeks ago by yzh

Minor comment: Shouldn't disjoint_union raise an error if the input is not disjoint?

It does.

sage: pc = PolyhedralComplex([Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)])])                     
sage: pc2 = PolyhedralComplex([Polyhedron(vertices=[(1, 1), (0, 0), (0, 1)])])                    
sage: pc.disjoint_union(pc2) 
ValueError: The given cells are not face-to-face

comment:27 follow-up: Changed 2 weeks ago by mkoeppe

But

sage: pc3 = PolyhedralComplex([Polyhedron(vertices=[(1, 1), (0, 0), (1, 0)])])
sage: pc2.disjoint_union(pc3)
Polyhedral complex with 2 maximal cells

comment:28 Changed 2 weeks ago by git

  • Commit changed from 752011fc6cb7e1ad97b6c4c675e3ba0533df3a91 to 27af45ad95dda448babc665b58181717dca6fa47

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

05e8f96add example where disjoint_union raisess an error if the input is not disjoint
27af45aTypos: interoir->interior, complexe->complex

comment:29 in reply to: ↑ 27 Changed 2 weeks ago by yzh

Replying to mkoeppe:

But

sage: pc3 = PolyhedralComplex([Polyhedron(vertices=[(1, 1), (0, 0), (1, 0)])])
sage: pc2.disjoint_union(pc3)
Polyhedral complex with 2 maximal cells

That looks correct to me.

comment:30 Changed 2 weeks ago by yzh

Ah, do you mean that pc2.disjoint_union(pc2) should raise an error?

comment:31 follow-up: Changed 2 weeks ago by mkoeppe

pc2 and pc3 are not disjoint, so this should be an error

comment:32 Changed 2 weeks ago by mkoeppe

sage: pc0 = PolyhedralComplex()
sage: pc0.ambient_dimension()
-1
sage: pc0.add_cell(Polyhedron(vertices=[(1, 1), (0, 0), (1, 0)]))
ValueError: The given cell is not a polyhedron in the same ambient space.

I think it would be better to add a keyword argument ambient_dim to __init__ so that one can set up an empty complex in the intended ambient space

Last edited 2 weeks ago by mkoeppe (previous) (diff)

comment:33 in reply to: ↑ 31 Changed 2 weeks ago by yzh

Good point! What I implemented in disjoint_union is actually the union, but not the disjoint union. Replying to mkoeppe:

pc2 and pc3 are not disjoint, so this should be an error

comment:34 Changed 2 weeks ago by git

  • Commit changed from 27af45ad95dda448babc665b58181717dca6fa47 to 372a10767ed2eb77b40a6ba0da6a77a576631b2d

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

cf7698cmethods disjoint_union and union
372a107add a keyword argument ambient_dim to __init__ so that one can set up an empty complex in the intended ambient space

comment:35 Changed 2 weeks ago by mkoeppe

My comments have all been addressed, thanks!

comment:36 Changed 2 weeks ago by tscrim

I agree that we can merge this without implementing the homology stuff. I have a few comments that should be addressed first:

  • It feels like there is a lot of overlap with the SimplicialComplex code. Do we want to refactor things to common base classes and/or use inheritance?
  • The bullet points for backend in PolyhedralComplex's doc are over-indented (back them up 2 spaces).
  • Not every method has a doctest, even if all they currently do is raise a NotImplementedError.
  • It would be good to include a message when you raise an error (see, e.g., the ValueError in PolyhedralComplex.__init__).
  • Error messages should start with a lowercase and not end with a period/full-stop. This is a Python convention we generally try to follow
  • Be consistent with how you do your documentation. I would not use the :param format personally.
  • I think the _an_element_ should raise an EmptySetError if it has no elements.

comment:37 Changed 2 weeks ago by git

  • Commit changed from 372a10767ed2eb77b40a6ba0da6a77a576631b2d to 0a40f1f841b07be7862f2a97c4cb501ccca451c2

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

0a40f1fimprove documentation and error messages

comment:38 Changed 2 weeks ago by yzh

Thanks, Travis! I revised the code according to your comments (expect for 1).

I agree that PolyhedralComplex and SimplicialComplex have many overlapping methods. As you may have noticed, these are methods required by the parent class GenericCellComplex. However, as one is geometric and the other is abstract, and due to the different ways that cells are stored inside the two complexes, I don't see how one can easily factor out a common base class etc.

comment:39 follow-up: Changed 2 weeks ago by jhpalmieri

Typo: "poyhedron" on about line 8.

I might change has_maximal_cell to is_maximal_cell. What do you think?

As far as refactoring goes, I see similar code but not identical code, so it would some work to reorganize things. That can be done on another ticket, in my opinion.

comment:40 in reply to: ↑ 39 ; follow-up: Changed 2 weeks ago by yzh

Replying to jhpalmieri:

Typo: "poyhedron" on about line 8.

Thanks for catching that!

I might change has_maximal_cell to is_maximal_cell. What do you think?

I once heard that self.is_xxx(other) means that "self is xxx of other". Therefore, in this case, I would think that cell.is_maximal_cell(polyhedralcomplex) and polyhedralcomplex.has_maximal_cell(cell). If this is not the convention in sage/homology, I'm happy to change the name to is_maximal_cell.

As far as refactoring goes, I see similar code but not identical code, so it would some work to reorganize things. That can be done on another ticket, in my opinion.

:)

Last edited 2 weeks ago by yzh (previous) (diff)

comment:41 Changed 2 weeks ago by git

  • Commit changed from 0a40f1f841b07be7862f2a97c4cb501ccca451c2 to f5be3fa7f178d9ab0390374781f8f16ca1b86b39

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

f5be3fafix typo

comment:42 in reply to: ↑ 40 Changed 2 weeks ago by jhpalmieri

Replying to yzh:

Replying to jhpalmieri:

I might change has_maximal_cell to is_maximal_cell. What do you think?

I once heard that self.is_xxx(other) means that "self is xxx of other". Therefore, in this case, I would think that cell.is_maximal_cell(polyhedralcomplex) and polyhedralcomplex.has_maximal_cell(cell). If this is not the convention in sage/homology, I'm happy to change the name to is_maximal_cell.

In simplicial_complex.py, the methods is_face and is_shelling_order use is... the way I'm suggesting. It's common for is_xxx(self) to be used the way you say, but not universal, and absolutely not universal for is_xxx(self, x, y, z), with more arguments.

comment:43 Changed 10 days ago by tscrim

A few things to do before I would set a positive review:

  • Add doctests for the NotImplementedError raising methods.
  • Change has_maximal_cell to is_maximal_cell because that is what the docstring is saying. If this was has_maximal_cell, I would expect it not to take any other arguments.
  • You can test plotting:
    sage: poset.plot(element_labels=d)                    # not tested
    
  • Change:
    -TESTS on nonbounded polyhedral complex::
    +For a nonbounded polyhedral complex::
    
  • Add a TestSuite(foo).run() to the __init__ doctests. (Not really necessary, but I like to see such a test there.)

comment:44 Changed 7 days ago by jhpalmieri

Also under discussion at #30400 and #31925: create a new directory sage/topology and move all files which deal with topological spaces there, leaving sage/homology for chain complexes and related tools. So perhaps this could be placed in sage/topology as well.

Note: See TracTickets for help on using tickets.