#31819 closed enhancement (fixed)

Only subfaces/supfaces for polyhedral face iterator

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.4
Component: geometry Keywords: face iterator, polyhedron
Cc: mkoeppe, yzh Merged in:
Authors: Jonathan Kliem Reviewers: Yuan Zhou, Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: 7f7e630 (Commits, GitHub, GitLab) Commit: 7f7e6301eb49ed48fd646beae85772344ba52338
Dependencies: #29683, #31245 Stopgaps:

Status badges

Description

We allow for the face iterator to only visit subsets of the current face.

Change History (36)

comment:1 Changed 21 months ago by gh-kliem

Dependencies: #29683
Status: newneeds_review

comment:2 Changed 21 months ago by git

Commit: a95f8d7c5fa17c1dd0076e0c8cb7398e82182d2e1cb1b7864dade6b479238c7db4dd9e66424382f1

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

69fcd71fix bug revealed by a_maximal_chain
1cb1b78fix error message in doctest

comment:3 Changed 21 months ago by git

Commit: 1cb1b7864dade6b479238c7db4dd9e66424382f12dc14f5f761f967f654434bd027d797566dfc9da

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

2dc14f5fix the order of the coatoms when resetting the face iterator

comment:4 Changed 21 months ago by mkoeppe

Cc: yzh added

comment:5 Changed 21 months ago by git

Commit: 2dc14f5f761f967f654434bd027d797566dfc9da2e41ed7294ae4a1a7517b1de051074c162217cb6

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

2e41ed7fix a variable name and add a doctest

comment:6 Changed 21 months ago by git

Commit: 2e41ed7294ae4a1a7517b1de051074c162217cb66ddf2284a5ae25d4680e78615e881df6ef5bf0d9

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

2a5a782expose in combinatorial_polyhedron
6cecfd7raise index error for index error; fix doctests
9a66e32expose in Polyhedron_base
977c088fix doctests
15e2c58improved documentation
deca8e0fix a variable name and add a doctest
be121adimplement only subfaces/supfaces for face iterator
ee42e98fix bug revealed by a_maximal_chain
05ec5b2fix error message in doctest
6ddf228fix the order of the coatoms when resetting the face iterator

comment:7 Changed 21 months ago by yzh

(Edited) You probably need to rebase this ticket on the #29683, or put face.ambient_H_indices(add_equations=False) everywhere.

Last edited 21 months ago by yzh (previous) (diff)

comment:8 Changed 21 months ago by yzh

Does this need to be changed to structure.highest_dimension? Or maybe I'm looking at a wrong version of the code.

cdef inline int next_face_loop(iter_t structure) nogil except -1:
    r"""
    See :meth:`FaceIterator.next_face_loop`.
    """
    if unlikely(structure.current_dimension == structure.dimension):
        # The function is not supposed to be called,
        # just prevent it from crashing.
        raise StopIteration
Last edited 21 months ago by yzh (previous) (diff)

comment:9 Changed 21 months ago by yzh

Does self.structure.dimension in cdef int find_face(self, face_t face) except -1 need changing?

comment:10 Changed 21 months ago by yzh

In face_iterator.pxd: New value 3 to be added to the comment

int face_status            # 0 not initialized, 1 initialized, 2 added to visited_all

comment:11 Changed 21 months ago by yzh

raise ValueError("cannot only visit subsets after ignoring a face")
raise ValueError("cannot ignore a face after setting iterator to only visit subsets")

I understood the first, but not the second. Why is it an error, rather than say that the iterator is consumed? I apologize if this is a silly question

comment:12 Changed 21 months ago by yzh

cdef int only_subsets(self) except -1:
    self.structure.highest_dimension = self.structure.current_dimension - 1

Why doesn't it prevent visiting the (sub) faces of dimension >= self.structure.current_dimension?

comment:13 Changed 21 months ago by git

Commit: 6ddf2284a5ae25d4680e78615e881df6ef5bf0d940d56400d156210c2c7c7b9751ac88b84b399acd

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

c3f028bcheck with a nice error for negative indices
110228ebetter check for the far face containment
ec79d1eimplement only subfaces/supfaces for face iterator
35c50d7fix bug revealed by a_maximal_chain
8609ee2fix error message in doctest
1f508a8fix the order of the coatoms when resetting the face iterator
b6e097ddo not display equations for doctests illustrating how the iterator works
ff87201update face status
a1b4c12consume the iterator if running ignore_subsets after only_subsets
40d5640specify for `find_face` that we assume the iterator to be clean

comment:14 in reply to:  11 Changed 21 months ago by gh-kliem

Replying to yzh:

raise ValueError("cannot only visit subsets after ignoring a face")
raise ValueError("cannot ignore a face after setting iterator to only visit subsets")

I understood the first, but not the second. Why is it an error, rather than say that the iterator is consumed? I apologize if this is a silly question

It's not a silly question and even if it where: You are reviewing the ticket and I'm very thankful for this. You have every right to ask silly questions.

Fixed.

comment:15 in reply to:  9 Changed 21 months ago by gh-kliem

Replying to yzh:

Does self.structure.dimension in cdef int find_face(self, face_t face) except -1 need changing?

I specified what I expect in find_face. It's a hidden cython method. So I think it is fine to assume things without checking.

It's not a terrible fail, if self.structure.highest_dimension was set. This would just be ignored in this case.

comment:16 in reply to:  8 ; Changed 21 months ago by gh-kliem

Replying to yzh:

Does this need to be changed to structure.highest_dimension? Or maybe I'm looking at a wrong version of the code.

cdef inline int next_face_loop(iter_t structure) nogil except -1:
    r"""
    See :meth:`FaceIterator.next_face_loop`.
    """
    if unlikely(structure.current_dimension == structure.dimension):
        # The function is not supposed to be called,
        # just prevent it from crashing.
        raise StopIteration

This just prevents segmentation fault. It's never supposed to happen anyway. In fact I can't even change this. Because when I set highest_dimension it will be equal to current_dimension. Only after running this, is current_dimension lower, if there are faces left.

comment:17 in reply to:  12 Changed 21 months ago by gh-kliem

Replying to yzh:

cdef int only_subsets(self) except -1:
    self.structure.highest_dimension = self.structure.current_dimension - 1

Why doesn't it prevent visiting the (sub) faces of dimension >= self.structure.current_dimension?

I don't understand the question.

next_dimension first calls next_face_loop. only_subsets makes sure that next_face_loop actually gets to the point of calling get_next_level (unless our face is the the only face left, than there are no new subfaces). If new_faces_counter is non-zero, the current dimension is lowered and it holds that current_dimension < highest_dimension.

If new_faces_counter is zero and there are no new subfaces, then next_face_loop returns 0 and next_dimension terminates as current_dimension = highest_dimension.

Whenever next_face_loop raises the dimension, it will return 0. This way next_dimension will in fact check, that we still have current_dimension <= highest_dimension.

comment:18 Changed 21 months ago by gh-kliem

Work issues: Merge conflict with #31245. One of them needs to be rebased.

comment:19 in reply to:  16 ; Changed 21 months ago by yzh

Replying to gh-kliem:

Replying to yzh:

Does this need to be changed to structure.highest_dimension? Or maybe I'm looking at a wrong version of the code.

cdef inline int next_face_loop(iter_t structure) nogil except -1:
    r"""
    See :meth:`FaceIterator.next_face_loop`.
    """
    if unlikely(structure.current_dimension == structure.dimension):
        # The function is not supposed to be called,
        # just prevent it from crashing.
        raise StopIteration

This just prevents segmentation fault. It's never supposed to happen anyway. In fact I can't even change this. Because when I set highest_dimension it will be equal to current_dimension. Only after running this, is current_dimension lower, if there are faces left.

I meant to change to if unlikely(self.structure.current_dimension > self.structure.highest_dimension): like all other checkings.

Sure, if it never happens, then the current version is fine.

comment:20 Changed 21 months ago by yzh

    if n_faces <= 1:
        # There will be no more faces from intersections.
        structure.current_dimension += 1
        return 0

What do you mean by "no more faces from intersections"? Why is it n_faces <= 1, not n_faces == 0, nor n_faces == 1?

comment:21 Changed 21 months ago by yzh

All other things on this ticket look good to me. Thanks for the explanations!

comment:22 in reply to:  19 ; Changed 21 months ago by gh-kliem

Replying to yzh:

Replying to gh-kliem:

Replying to yzh:

Does this need to be changed to structure.highest_dimension? Or maybe I'm looking at a wrong version of the code.

cdef inline int next_face_loop(iter_t structure) nogil except -1:
    r"""
    See :meth:`FaceIterator.next_face_loop`.
    """
    if unlikely(structure.current_dimension == structure.dimension):
        # The function is not supposed to be called,
        # just prevent it from crashing.
        raise StopIteration

This just prevents segmentation fault. It's never supposed to happen anyway. In fact I can't even change this. Because when I set highest_dimension it will be equal to current_dimension. Only after running this, is current_dimension lower, if there are faces left.

I meant to change to if unlikely(self.structure.current_dimension > self.structure.highest_dimension): like all other checkings.

Sure, if it never happens, then the current version is fine.

That's what I figure you meant. But it does not work. E.g. when you want to only visit the elements below the first facet, the highest dimension will be set to d-2. But current dimension is d-1. Only after next_face_loop is called has the dimension changed to d-2. This is different from the start. At the start the facets are already known and hence the dimension starts at d-1. But when you want to visit everything below something, the elements below have not been computed yet.

I could set this up differently, if you find it confusing and make only_subsets call next_face_loop once.

comment:23 in reply to:  20 ; Changed 21 months ago by gh-kliem

Replying to yzh:

    if n_faces <= 1:
        # There will be no more faces from intersections.
        structure.current_dimension += 1
        return 0

What do you mean by "no more faces from intersections"? Why is it n_faces <= 1, not n_faces == 0, nor n_faces == 1?

The intersections are obtained by intersecting the last face with each previous ones. If there is only one face, we can stop and don't need get_next_level to tell us that there are no intersections.

I don't think n_faces == 0 can happen, but it is better to be safe than sorry. Because get_next_level will intersect the last face with all previous ones. If there is zero faces we have an overflow and the face 2^64-1 is intersected with all previous once, which will result in an segmentation fault.

But maybe it is better to handle this check as a first thing in get_next_level. This is probably where it belongs anyway. What do you think?

comment:24 in reply to:  22 Changed 21 months ago by yzh

Replying to gh-kliem:

That's what I figure you meant. But it does not work. E.g. when you want to only visit the elements below the first facet, the highest dimension will be set to d-2. But current dimension is d-1. Only after next_face_loop is called has the dimension changed to d-2. This is different from the start. At the start the facets are already known and hence the dimension starts at d-1. But when you want to visit everything below something, the elements below have not been computed yet.

I could set this up differently, if you find it confusing and make only_subsets call next_face_loop once.

Thank you for the patient answer! It makes sense to me now.

comment:25 in reply to:  23 Changed 21 months ago by yzh

Reviewers: Yuan Zhou
Status: needs_reviewpositive_review

Replying to gh-kliem:

The intersections are obtained by intersecting the last face with each previous ones. If there is only one face, we can stop and don't need get_next_level to tell us that there are no intersections.

I don't think n_faces == 0 can happen, but it is better to be safe than sorry. Because get_next_level will intersect the last face with all previous ones. If there is zero faces we have an overflow and the face 2^64-1 is intersected with all previous once, which will result in an segmentation fault.

But maybe it is better to handle this check as a first thing in get_next_level. This is probably where it belongs anyway. What do you think?

I thought that n_faces == 0 couldn't happen too; that's why I asked, in case I missed/misunderstood something. I was also wondering about the order of the if checks in next_face_loop, but I figured out that it doesn't really matter. Besides, next_face_loop and get_next_level are not objects of this ticket. The current implementation works well, so I don't think more changes are needed.

comment:26 Changed 21 months ago by gh-kliem

Status: positive_reviewneeds_work

Thank you.

However, I will set this on "needs work" due to merge conflict with #31245. Depending on whether #31245 gets in or not, I will either rebase here or rebase #31245 and then put it back on "positive review".

comment:27 Changed 20 months ago by mkoeppe

Ready to merge #31245?

comment:28 Changed 20 months ago by gh-kliem

I don't know, if #31245 will be rejected again. But it looks like it's done now. It just triggered an unrelated bug.

What is the best way to proceed from here? I could just create a branch for this ticket here on top of #31245 and can always go back to the old branch if that fails.

comment:29 Changed 20 months ago by mkoeppe

Sure, it's easy to just back out the merge if necessary

comment:30 Changed 20 months ago by gh-kliem

Branch: u/gh-kliem/only_subsetsu/gh-kliem/only_subsets_reb
Commit: 40d56400d156210c2c7c7b9751ac88b84b399acdd073ca56b926a795c5a22490aa9644accb7f9a1c
Status: needs_workneeds_review

Last 10 new commits:

70a8791Merge branch 'u/gh-kliem/check_openmp_at_configuration' of git://trac.sagemath.org/sage into u/gh-kliem/first_parallel_version_of_face_iterator_reb2
fdbe95fuse cython.parallel.threadid instead of omp_get_thread_num
4ae6966Merge tag '9.4.beta0' into t/31245/first_parallel_version_of_face_iterator_reb2
bfb4efbMerge branch 'u/mkoeppe/first_parallel_version_of_face_iterator_reb2' of git://trac.sagemath.org/sage into u/mkoeppe/first_parallel_version_of_face_iterator_reb3
4c0a4aeinitialize do_f_vector
9119d8emerge in #31245
5dc2c8cmerge in public/31834
f1270b0Merge branch 'public/31834-reb' of git://trac.sagemath.org/sage into public/31834-reb2
297792aequalities -> equations for #31821 as well
d073ca5Merge branch 'public/31834-reb2' of git://trac.sagemath.org/sage into u/gh-kliem/only_subsets_reb

comment:31 Changed 20 months ago by gh-kliem

Dependencies: #29683#29683, #31245
Work issues: Merge conflict with #31245. One of them needs to be rebased.

Rebased on #31245 and new version of #29683.

Needed to fix max_dim in next_dimension because of #31245.

comment:32 Changed 20 months ago by gh-kliem

Branch: u/gh-kliem/only_subsets_rebu/gh-kliem/only_subsets_reb2
Commit: d073ca56b926a795c5a22490aa9644accb7f9a1c542baee396e8db57d59020cc1fd905e1b045eaa7

Actually rebasing on new version of #29683 and then pulling in #31245.


Last 10 new commits:

99ddc2fbetter check for the far face containment
0f78d2aimplement only subfaces/supfaces for face iterator
6c88068fix bug revealed by a_maximal_chain
b72578bfix error message in doctest
ad75abbfix the order of the coatoms when resetting the face iterator
3d158addo not display equations for doctests illustrating how the iterator works
353313cupdate face status
842fb8econsume the iterator if running ignore_subsets after only_subsets
250f0e4specify for `find_face` that we assume the iterator to be clean
542baeemerge in #31245

comment:33 Changed 20 months ago by mkoeppe

Branch: u/gh-kliem/only_subsets_reb2u/mkoeppe/only_subsets_reb2

comment:34 Changed 20 months ago by mkoeppe

Commit: 542baee396e8db57d59020cc1fd905e1b045eaa77f7e6301eb49ed48fd646beae85772344ba52338
Reviewers: Yuan ZhouYuan Zhou, Matthias Koeppe
Status: needs_reviewpositive_review

Back to positive review. LGTM


New commits:

3e0229fMerge tag '9.4.beta3' into t/31834/public/31834-reb2
8190917Merge #31834
7f7e630Merge #29683

comment:35 Changed 20 months ago by gh-kliem

Thank you.

comment:36 Changed 19 months ago by vbraun

Branch: u/mkoeppe/only_subsets_reb27f7e6301eb49ed48fd646beae85772344ba52338
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.