PolyhedralComplex

[yuan-zhou]

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

CC: @mkoeppe @jhpalmieri @jplab @tscrim

Component: geometry

Keywords: polyhedral complex

Author: Yuan Zhou

Branch/Commit: 32d34b7

Reviewer: John Palmieri, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/31748

[yuan-zhou]

Branch: u/yzh/polyhedralcomplex

[mkoeppe]

Commit: f76287b

[mkoeppe]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-Create (geometric) PolyhedralComplex, whose cells are Sage Polyhedra. 
+Create (geometric) `PolyhedralComplex`, whose cells are Sage Polyhedra. 

[mkoeppe]

New commits:

f76287b

initial implementation of polyhedral_complex.py

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

577456a

make tox happy

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f76287b to 577456a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

38aaf75

add doc for html build

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 577456a to 38aaf75

[mkoeppe]

comment:6

add author name so that the patchbot runs

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

22c9024

new methods product, disjoint_union, join

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 38aaf75 to 22c9024

[yuan-zhou]

Author: Yuan Zhou

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

add1ec2	change `_repr_` to show only maximal cells
614dd2d	rename maximal_cells_list to maximal_cells_sorted, and rename cells_list to cells_sorted
0bd4042	is_immutable default is False, set_immutable()

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 22c9024 to 0bd4042

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0bd4042 to 18c1a33

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3cc98f5	improve `_repr_`, factor out cells_list_to_cells_dict
18c1a33	def add_cell

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 18c1a33 to 45f080c

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

45f080c

implement PolyhedralComplex.remove_cell()

[yuan-zhou]

comment:12

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 45f080c to dfe5cb8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

33be3ab	implement subdivide, is_simplicial_complex, is_polyhedral_fan, is_simplicial_fan; allow 3d plot
dfe5cb8	make backend optional argument to PolyhedralComplex

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from dfe5cb8 to 752011f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

752011f

zero is followed by plural countable nouns

[jhpalmieri]

comment:16

Replying to @yuan-zhou:

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.

[jhpalmieri]

comment:17

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.

[mkoeppe]

comment:18

That would be #31842 - CombinatorialPolyhedralComplex

[mkoeppe]

comment:19

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

[tscrim]

comment:20

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.

[yuan-zhou]

comment:21

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

[yuan-zhou]

comment:22

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.

[jhpalmieri]

comment:23

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?

[jhpalmieri]

comment:24

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

[mkoeppe]

comment:25

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

[yuan-zhou]

comment:26

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

[mkoeppe]

comment:27

But

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 752011f to 27af45a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

05e8f96	add example where disjoint_union raisess an error if the input is not disjoint
27af45a	Typos: interoir->interior, complexe->complex

[yuan-zhou]

comment:29

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.

[yuan-zhou]

comment:30

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

[mkoeppe]

comment:31

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

[mkoeppe]

comment:32

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

[yuan-zhou]

comment:33

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

cf7698c	methods disjoint_union and union
372a107	add a keyword argument ambient_dim to `__init__` so that one can set up an empty complex in the intended ambient space

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 27af45a to 372a107

[mkoeppe]

comment:35

My comments have all been addressed, thanks!

[tscrim]

comment:36

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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0a40f1f

improve documentation and error messages

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 372a107 to 0a40f1f

[yuan-zhou]

comment:38

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.

[jhpalmieri]

comment:39

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.