Opened 5 years ago
Closed 5 years ago
#19892 closed enhancement (fixed)
Face semigroup of hyperplane arrangement
Reported by:  darij  Owned by:  

Priority:  major  Milestone:  sage7.1 
Component:  geometry  Keywords:  hyperplane arrangements, semigroups, polyhedra 
Cc:  dperkinson, Stefan, ncohen, rbeezer, vbraun, nthiery, saliola  Merged in:  
Authors:  Darij Grinberg  Reviewers:  Miguel Marco 
Report Upstream:  N/A  Work issues:  
Branch:  5087d23 (Commits)  Commit:  5087d232b87843f6181ed0feea50c8ffb553c7ec 
Dependencies:  Stopgaps: 
Description
The branch implements the closed faces of a hyperplane arrangement, the multiplication of the face semigroup, and its semigroup algebra.
The semigroup itself is not implemented, since I cannot find a way to build a finite semigroup (or magma) out of a multiplication table. I could make this myself, but I feel stupid doing this, as I would likely just duplicate something existing (and not very well, as I still don't grok the category framework). I *can* add it if you want me to.
Change History (19)
comment:1 Changed 5 years ago by
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
 Milestone changed from sage7.0 to sage7.1
comment:3 Changed 5 years ago by
comment:4 followup: ↓ 5 Changed 5 years ago by
I am going through the code, but there are some explanations I don't fully understand. For instance, can you give an example of the phnomenon explained in
# Do not append ``zero_part`` yet! It might be # redundant (in the sense that some of its defining # inequalities are always equalities on it). Check for # this:
please?
comment:5 in reply to: ↑ 4 ; followup: ↓ 8 Changed 5 years ago by
Replying to mmarco:
I am going through the code, but there are some explanations I don't fully understand. For instance, can you give an example of the phnomenon explained in
# Do not append ``zero_part`` yet! It might be # redundant (in the sense that some of its defining # inequalities are always equalities on it). Check for # this:please?
When your hyperplanes have the equations x == 0, y == 0 and x + y == 0, then the face (x == 0 & y == 0) of the hyperplane arrangement formed by the first two will intersect the halfspace x + y >= 0 in itself, and we want to record this as a 0 sign, not as a +1 sign. Remember that all the faces here are closed faces.
Sorry for the doc bug! If you could fix this (in the hopefully obvious way; I tend to get the "::"s wrong in docstrings), I'd be really grateful.
comment:6 followup: ↓ 7 Changed 5 years ago by
(I think it's the EXAMPLES with only one colon in the docstring face_semigroup_algebra that is breaking the docbuild.)
comment:7 in reply to: ↑ 6 Changed 5 years ago by
Replying to darij:
(I think it's the EXAMPLES with only one colon in the docstring face_semigroup_algebra that is breaking the docbuild.)
That appears to be the problem from my quick look over.
comment:8 in reply to: ↑ 5 Changed 5 years ago by
When your hyperplanes have the equations x == 0, y == 0 and x + y == 0, then the face (x == 0 & y == 0) of the hyperplane arrangement formed by the first two will intersect the halfspace x + y >= 0 in itself, and we want to record this as a 0 sign, not as a +1 sign. Remember that all the faces here are closed faces.
But wouldn't that case already be covered by this section?
if zero_part_dim == face_dim: # If the intersection of ``face`` with ``hyperplane`` # has the same dimension as ``face``, then this # intersection *is* ``face``, so we can continue # (without adding the other two intersections, since # those are empty): subdivided.append((signs + (0,), face)) continue
Also, I added the missing colons, but still the doc building complains.
comment:9 followup: ↓ 10 Changed 5 years ago by
 Reviewers set to Miguel Marco
 Status changed from needs_review to needs_work
Nevermind, I understood the logic behind it now.
The code looks correct to me. But I have a couple suggestions/comments/questions:
 The way to construct the closed faces seems a bit overcomplicated. My impression is that a recursive approach (take the delition of the last hyperplane, compute the closed faces, and then intersect them with the three sides of the deleted hyperplane) would probably be simpler (but maybe slower). Did you consider it?
 I think that the semigroup algebra should provide an option to provide the names of the generators.
comment:10 in reply to: ↑ 9 ; followup: ↓ 16 Changed 5 years ago by
Thanks for looking through this, Miguel!
Replying to mmarco:
The code looks correct to me. But I have a couple suggestions/comments/questions:
 The way to construct the closed faces seems a bit overcomplicated. My impression is that a recursive approach (take the delition of the last hyperplane, compute the closed faces, and then intersect them with the three sides of the deleted hyperplane) would probably be simpler (but maybe slower). Did you consider it?
Isn't this what I am doing? Or do you want me to make the method fully recursive, i.e., build a hyperplane arrangement out of the first n1 hyperplanes, then call the closed_faces
method on that, and then just cut with the last hyperplane? I think that wouldn't be any faster than what I have done, plus I am not sure that it would work, because when you call HyperplaneArrangement
the hyperplanes are getting sorted in some way, and I'm not sure whether removing a hyperplane wouldn't mess up the order of the remaining ones.
 I think that the semigroup algebra should provide an option to provide the names of the generators.
Good point, done.
I'll take care of the doc shortly, once it's done building.
comment:11 Changed 5 years ago by
 Commit changed from 2ba781d9bec2db5d4e088a528729d3dbfaa11952 to 2986da3b369c0d96d8c2409dd6756026018d68d0
comment:12 Changed 5 years ago by
 Commit changed from 2986da3b369c0d96d8c2409dd6756026018d68d0 to 53704ecd007743ded8d99c9ba90673c004229b70
Branch pushed to git repo; I updated commit sha1. New commits:
53704ec  doc fix

comment:13 Changed 5 years ago by
 Status changed from needs_work to needs_review
The doc seems to build now  canyou confirm?
comment:14 Changed 5 years ago by
The doc seems to build now  canyou confirm?
comment:15 Changed 5 years ago by
 Commit changed from 53704ecd007743ded8d99c9ba90673c004229b70 to 5087d232b87843f6181ed0feea50c8ffb553c7ec
Branch pushed to git repo; I updated commit sha1. New commits:
5087d23  oops

comment:16 in reply to: ↑ 10 Changed 5 years ago by
Isn't this what I am doing? Or do you want me to make the method fully recursive, i.e., build a hyperplane arrangement out of the first n1 hyperplanes, then call the
closed_faces
method on that, and then just cut with the last hyperplane? I think that wouldn't be any faster than what I have done, plus I am not sure that it would work, because when you callHyperplaneArrangement
the hyperplanes are getting sorted in some way, and I'm not sure whether removing a hyperplane wouldn't mess up the order of the remaining ones.
Yes, that is what i meant. I don't think it will be faster than what you do, but maybe more readable. Anyways, if there is some problem with the ordering, it is probably better to leave it the way it is.
comment:17 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:18 Changed 5 years ago by
Aaand thanks again!!
comment:19 Changed 5 years ago by
 Branch changed from public/ticket/19892 to 5087d232b87843f6181ed0feea50c8ffb553c7ec
 Resolution set to fixed
 Status changed from positive_review to closed
I am getting errors when generating the documentation: