Opened 11 months ago
Last modified 5 days ago
#30438 needs_work enhancement
Improve face iterator for almost simple/simplicial polytopes
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.5 
Component:  geometry  Keywords:  simple, simplicial, face iterator, polytope 
Cc:  jipilab, ghLaisRast, tscrim  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/ghkliem/face_iterator_simple_face_2 (Commits, GitHub, GitLab)  Commit:  d3c9384363f49e54f8a3d1bb84e626d58a277cee 
Dependencies:  #30040, #30435  Stopgaps: 
Description (last modified by )
#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 (16)
comment:1 Changed 11 months ago by
 Branch set to u/ghkliem/face_iterator_simple_face
 Commit set to e0d117a0b2d2dcdefe311dca5a328db9382dcb1e
comment:2 Changed 11 months ago by
 Description modified (diff)
comment:3 Changed 11 months ago by
 Description modified (diff)
comment:4 Changed 11 months ago by
 Commit changed from e0d117a0b2d2dcdefe311dca5a328db9382dcb1e to 59f6a1268eaae0ba02241d606d06ee3bd95e7e1f
Branch pushed to git repo; I updated commit sha1. New commits:
59f6a12  improved documentation

comment:5 Changed 11 months ago by
 Cc jipilab ghLaisRast tscrim added
 Status changed from new to needs_review
comment:6 Changed 11 months ago by
 Dependencies changed from #30040, #30045 to #30040, #30435
comment:7 Changed 11 months ago by
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 11 months ago by
 Commit changed from 59f6a1268eaae0ba02241d606d06ee3bd95e7e1f to 56ba0e085fa841b9158e488392b05925a84e3a4b
comment:9 Changed 11 months ago by
 Branch changed from u/ghkliem/face_iterator_simple_face to u/ghkliem/face_iterator_simple_face_2
 Commit changed from 56ba0e085fa841b9158e488392b05925a84e3a4b to 79a866639e5b312608416cec5e0340f242c82fee
Changes from #30040.
Last 10 new commits:
ed6e966  improvements in documentation

bf91483  improved count atoms

7bab490  Merge branch 'u/ghkliem/improved_count_atoms' of git://trac.sagemath.org/sage into u/ghkliem/face_iterator_simple_face_2

d9aca3b  simpler algorithm for many simple faces

3550857  sort the faces according to being simple

19b293c  small improvements

b6e4659  small improvements

d4a9fd2  compile warning in doctest

de36d26  two bugs

79a8666  improved documentation

comment:11 Changed 11 months ago by
 Commit changed from 79a866639e5b312608416cec5e0340f242c82fee to d3c9384363f49e54f8a3d1bb84e626d58a277cee
Branch pushed to git repo; I updated commit sha1. New commits:
d3c9384  Merge branch 'develop' of git://trac.sagemath.org/sage into u/ghkliem/face_iterator_simple_face_2

comment:12 Changed 11 months ago by
 Status changed from needs_work to needs_review
comment:13 Changed 11 months ago by
 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 9 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:15 Changed 5 months ago by
 Milestone changed from sage9.3 to sage9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:16 Changed 5 days ago by
 Milestone changed from sage9.4 to sage9.5
Setting a new milestone for this ticket based on a cursory review.
Last 10 new commits:
improvements in documentation
changes in 30429
typo
simpler algorithm for many simple faces
sort the faces according to being simple
small improvements
improved count atoms
small improvements
compile warning in doctest
two bugs