Opened 4 years ago

Closed 3 years ago

#19892 closed enhancement (fixed)

Face semigroup of hyperplane arrangement

Reported by: darij Owned by:
Priority: major Milestone: sage-7.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 3 years ago by darij

  • Status changed from new to needs_review

comment:2 Changed 3 years ago by darij

  • Milestone changed from sage-7.0 to sage-7.1

comment:3 Changed 3 years ago by mmarco

I am getting errors when generating the documentation:

...
[geometry ] loading cross citations...
[geometry ] /home/mmarco/sage/local/lib/python2.7/site-packages/sage/geometry/hyperplane_arrangement/arrangement.py:docstring of sage.geometry.hyperplane_arrangement.arrangement:27: ERROR: Unexpected indentation.
[geometry ] /home/mmarco/sage/local/lib/python2.7/site-packages/sage/geometry/hyperplane_arrangement/arrangement.py:docstring of sage.geometry.hyperplane_arrangement.arrangement.HyperplaneArrangementElement.face_semigroup_algebra:42: WARNING: Block quote ends without a blank line; unexpected unindent.
Error building the documentation.

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

comment:5 in reply to: ↑ 4 ; follow-up: Changed 3 years ago by darij

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 follow-up: Changed 3 years ago by darij

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

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 3 years ago by mmarco

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 follow-up: Changed 3 years ago by mmarco

  • 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 ; follow-up: Changed 3 years ago by darij

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 n-1 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 3 years ago by git

  • Commit changed from 2ba781d9bec2db5d4e088a528729d3dbfaa11952 to 2986da3b369c0d96d8c2409dd6756026018d68d0

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

b3208d3Merge branch 'public/ticket/19892' of git://trac.sagemath.org/sage into hyp2
2986da3naming the basis of semigroup algebra

comment:12 Changed 3 years ago by git

  • Commit changed from 2986da3b369c0d96d8c2409dd6756026018d68d0 to 53704ecd007743ded8d99c9ba90673c004229b70

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

53704ecdoc fix

comment:13 Changed 3 years ago by darij

  • Status changed from needs_work to needs_review

The doc seems to build now -- canyou confirm?

comment:14 Changed 3 years ago by darij

The doc seems to build now -- canyou confirm?

comment:15 Changed 3 years ago by git

  • Commit changed from 53704ecd007743ded8d99c9ba90673c004229b70 to 5087d232b87843f6181ed0feea50c8ffb553c7ec

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

5087d23oops

comment:16 in reply to: ↑ 10 Changed 3 years ago by mmarco

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 n-1 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.

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 3 years ago by mmarco

  • Status changed from needs_review to positive_review

comment:18 Changed 3 years ago by darij

Aaand thanks again!!

comment:19 Changed 3 years ago by vbraun

  • Branch changed from public/ticket/19892 to 5087d232b87843f6181ed0feea50c8ffb553c7ec
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.