Opened 8 months ago

Last modified 2 months ago

#30438 needs_work enhancement

Improve face iterator for almost simple/simplicial polytopes

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.4
Component: geometry Keywords: simple, simplicial, face iterator, polytope
Cc: jipilab, gh-LaisRast, tscrim Merged in:
Authors: Jonathan Kliem Reviewers:
Report Upstream: N/A Work issues:
Branch: u/gh-kliem/face_iterator_simple_face_2 (Commits, GitHub, GitLab) Commit: d3c9384363f49e54f8a3d1bb84e626d58a277cee
Dependencies: #30040, #30435 Stopgaps:

Status badges

Description (last modified by gh-kliem)

#30040 improved the face iterator for simple/simplicial polytopes.

Actually, the same trick can be applied for simple faces. (Note that the iterator treats simplicial polytopes dually).

If a face is simple, then any intersections of it's facets is one of it's ridges or empty.

As this helps only sporadically, we cannot afford to compute for each face if it is simple. However, a cheap certificate of a face being simple is that it only contains "simple vertices" (with vertex figure a simplex).

Now, at initialization the face iterator computes those "simple vertices" and checks inclusion of each face to determine if it is simple (if not at least 10 percent of the vertices we skip this check). If a face is simple, we can skip the costly inclusion checks.

Before this ticket:

sage: P = polytopes.permutahedron(7)                                                                                                                                                                                                                                                                                                                                       
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 257 ms, sys: 7 µs, total: 257 ms
Wall time: 257 ms
(1, 5041, 16251, 19761, 11144, 2860, 267, 1)

sage: P = polytopes.associahedron(['A',7])                                                                                                                                                                                                                                                                                                                                 
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 13.5 ms, sys: 0 ns, total: 13.5 ms
Wall time: 13.4 ms
(1, 1431, 5977, 10177, 9040, 4440, 1163, 134, 1)
sage: P = polytopes.hypercube(12)                                                                                                                                                                                                                                                                                                                                          
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 419 ms, sys: 17 µs, total: 419 ms
Wall time: 419 ms
(1, 4097, 28669, 92125, 180037, 238755, 226776, 158466, 82170, 31350, 8525, 1529, 145, 1)

sage: P = polytopes.permutahedron(7)                                                                                                                                                                                                                                                                                                                                       
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 79.5 ms, sys: 0 ns, total: 79.5 ms
Wall time: 79.3 ms
(1, 5041, 16251, 19761, 11144, 2860, 267, 1)

sage: P = polytopes.associahedron(['A',7])                                                                                                                                                                                                                                                                                                                                 
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 9.85 ms, sys: 0 ns, total: 9.85 ms
Wall time: 9.72 ms
(1, 1431, 5977, 10177, 9040, 4440, 1163, 134, 1)

sage: P = polytopes.hypercube(12)                                                                                                                                                                                                                                                                                                                                          
sage: P1 = P.stack(next(P.face_generator(1)))                                                                                                                                                                                                                                                                                                                              
sage: C = CombinatorialPolyhedron(P1)                                                                                                                                                                                                                                                                                                                                      
sage: %time C.f_vector()                                                                                                                                                                                                                                                                                                                                                   
CPU times: user 391 ms, sys: 0 ns, total: 391 ms
Wall time: 391 ms
(1, 4097, 28669, 92125, 180037, 238755, 226776, 158466, 82170, 31350, 8525, 1529, 145, 1)

Note that for the last instance, there isn't a significant amount of simple vertices so the old approach is chosen.

Change History (15)

comment:1 Changed 8 months ago by gh-kliem

  • Branch set to u/gh-kliem/face_iterator_simple_face
  • Commit set to e0d117a0b2d2dcdefe311dca5a328db9382dcb1e

Last 10 new commits:

0297853improvements in documentation
7ffac00changes in 30429
01b4154typo
34a74b8simpler algorithm for many simple faces
c9165b0sort the faces according to being simple
b9dc7e1small improvements
5dbe710improved count atoms
e88c28csmall improvements
a50be39compile warning in doctest
e0d117atwo bugs

comment:2 Changed 8 months ago by gh-kliem

  • Description modified (diff)

comment:3 Changed 8 months ago by gh-kliem

  • Description modified (diff)

comment:4 Changed 8 months ago by git

  • Commit changed from e0d117a0b2d2dcdefe311dca5a328db9382dcb1e to 59f6a1268eaae0ba02241d606d06ee3bd95e7e1f

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

59f6a12improved documentation

comment:5 Changed 8 months ago by gh-kliem

  • Cc jipilab gh-LaisRast tscrim added
  • Status changed from new to needs_review

comment:6 Changed 8 months ago by gh-kliem

  • Dependencies changed from #30040, #30045 to #30040, #30435

comment:7 Changed 8 months ago by gh-kliem

A remark to cythonizing and compiling:

  • Current version:
    +            foo = self.atoms.data
    +            atoms_face_length = self.atoms.face_length
    +
    +            counter = 0
    +            for j in range(self.atoms.n_faces):
    +                if count_atoms(foo[j], atoms_face_length) == self.structure.dimension:
    +                    counter += 1
    +                    self.structure.simple_vertices[j//64] |= vertex_to_bit_dictionary(j % 64)
    
  • Much slower:
    +            counter = 0
    +            for j in range(self.atoms.n_faces):
    +                if count_atoms(self.atoms.data[j], self.atoms.face_length) == self.structure.dimension:
    +                    counter += 1
    +                    self.structure.simple_vertices[j//64] |= vertex_to_bit_dictionary(j % 64)
    
  • As fast as the current version:
    +            counter = 0
    +            for j in range(self.atoms.n_faces):
    +                if count_atoms(self.atoms.data[j], self.atoms.face_length) == self.structure.dimension:
    +                    counter += 1
    +                    self.structure.simple_vertices[j//64] |= vertex_to_bit_dictionary(j % 64)
    +
    +            for j in range(self.atoms.n_faces):
    +                if count_atoms(self.atoms.data[j], self.atoms.face_length) == self.structure.dimension:
    +                    self.structure.simple_vertices[j//64] |= vertex_to_bit_dictionary(j % 64)
    

I guess looking up self.atoms takes significant amount of time. What is suprising is that when you add a useless loop, things speed up. Either by cythonizing or compiling (I didn't check) it is figured, that we need the properties of self.atoms more often and this is optimized then.

Perhaps even more suprising. When you add

# cython: profile=True
# cython: linetrace=True
# distutils: define_macros=CYTHON_TRACE_NOGIL=1
# distutils: define_macros=CYTHON_TRACE=1

to the beginning of base.pyx the second version is just as fast. Makes it hard to profile where the difference in performance is, when it goes away when profiling.

comment:8 Changed 8 months ago by git

  • Commit changed from 59f6a1268eaae0ba02241d606d06ee3bd95e7e1f to 56ba0e085fa841b9158e488392b05925a84e3a4b

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

20a39b6outsource inclusion maximal
b672fcaremoved redundant function
f62e770merge in #30458
accea52missing }
56ba0e0merge in #30040

comment:9 Changed 8 months ago by gh-kliem

  • Branch changed from u/gh-kliem/face_iterator_simple_face to u/gh-kliem/face_iterator_simple_face_2
  • Commit changed from 56ba0e085fa841b9158e488392b05925a84e3a4b to 79a866639e5b312608416cec5e0340f242c82fee

Changes from #30040.


Last 10 new commits:

ed6e966improvements in documentation
bf91483improved count atoms
7bab490Merge branch 'u/gh-kliem/improved_count_atoms' of git://trac.sagemath.org/sage into u/gh-kliem/face_iterator_simple_face_2
d9aca3bsimpler algorithm for many simple faces
3550857sort the faces according to being simple
19b293csmall improvements
b6e4659small improvements
d4a9fd2compile warning in doctest
de36d26two bugs
79a8666improved documentation

comment:10 Changed 7 months ago by mkoeppe

  • Status changed from needs_review to needs_work

needs rebase

comment:11 Changed 7 months ago by git

  • Commit changed from 79a866639e5b312608416cec5e0340f242c82fee to d3c9384363f49e54f8a3d1bb84e626d58a277cee

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

d3c9384Merge branch 'develop' of git://trac.sagemath.org/sage into u/gh-kliem/face_iterator_simple_face_2

comment:12 Changed 7 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:13 Changed 7 months ago by gh-kliem

  • Status changed from needs_review to needs_work

I want to redesign some of the setup before making everything more complicated.

More precisely, creating strucutures face_struct and faces_list_struct that take care of the details. Then this overly long argument list of get_next_level will just reduce to three arguments or so. This would also make future changes easier including the transition to bitsets.pxi.

comment:14 Changed 6 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:15 Changed 2 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

Note: See TracTickets for help on using tickets.