id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
30040 Improve face iterator for simple/simplicial polytopes gh-kliem "So far the face iterator for polyhedra assumes the diamond property of the lattice only. The special case of simple/simplicial polytopes is not exploited. In this case all intervals not containing zero of the lattice are boolean (for simplicial polytopes we use the dual algorithm).
We alter the algorithm to work for lattices where every interval not containing zero is a boolean sublattice. We may even drop any further conditions on the lattice. So we may apply the algorithm to lattices, where some ""edges"" have only one atom.
Thus the algorithm can in principle be applied to simplicial complexes now in dual mode (""edges"" with a single atom correspond to ""ridges"" only contained in one maximal face). The key observations are:
- To check whether an intersection of faces is zero, we check whether the atom-representation is zero. Although not unique (in case the diamond property is relaxed), it works to distinguish from zero.
- To intersect we now additionally unite the coatom representation. This gives the correct representation of the new face unless the intersection is zero.
- An intersection of two facets has always codimension 1, if not empty (they contain a common atom and are thus contained in a common boolean sublattice).
- To mark a face as visited, we save its coatom representation in `visited_all_coatom_rep`.
- To check whether we have seen a face already, we check containment of the coatom representation.
This algorithm performs much better and is also asymptotically better.
Before this ticket:
{{{
sage: P = polytopes.permutahedron(7)
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 85.7 ms, sys: 0 ns, total: 85.7 ms
Wall time: 85.1 ms
(1, 5040, 15120, 16800, 8400, 1806, 126, 1)
sage: P = polytopes.associahedron(['A',9], backend='normaliz')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 1.11 s, sys: 23 µs, total: 1.11 s
Wall time: 1.11 s
(1, 16796, 75582, 143208, 148512, 91728, 34398, 7644, 936, 54, 1)
sage: P = polytopes.associahedron(['A',10], backend='normaliz')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 21 s, sys: 19.8 ms, total: 21 s
Wall time: 21 s
(1, 58786, 293930, 629850, 755820, 556920, 259896, 76440, 13650, 1365, 65, 1)
sage: P = polytopes.hypercube(14, backend='field')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 5.27 s, sys: 11.9 ms, total: 5.28 s
Wall time: 5.27 s
(1, 16384, 114688, 372736, 745472, 1025024, 1025024, 768768, 439296, 192192, 64064, 16016, 2912, 364, 28, 1)
sage: P = polytopes.hypercube(16, backend='field')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 3min 11s, sys: 152 ms, total: 3min 11s
Wall time: 3min 11s
(1, 65536, 524288, 1966080, 4587520, 7454720, 8945664, 8200192, 5857280, 3294720, 1464320, 512512, 139776, 29120, 4480, 480, 32, 1)
}}}
With this ticket:
{{{
sage: P = polytopes.permutahedron(7)
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 15.5 ms, sys: 0 ns, total: 15.5 ms
Wall time: 15.5 ms
(1, 5040, 15120, 16800, 8400, 1806, 126, 1)
sage: P = polytopes.associahedron(['A',9], backend='normaliz')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 161 ms, sys: 14 µs, total: 161 ms
Wall time: 161 ms
(1, 16796, 75582, 143208, 148512, 91728, 34398, 7644, 936, 54, 1)
sage: P = polytopes.associahedron(['A',10], backend='normaliz')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 2.17 s, sys: 0 ns, total: 2.17 s
Wall time: 2.17 s
(1, 58786, 293930, 629850, 755820, 556920, 259896, 76440, 13650, 1365, 65, 1)
sage: P = polytopes.hypercube(14, backend='field')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 1.1 s, sys: 0 ns, total: 1.1 s
Wall time: 1.1 s
(1, 16384, 114688, 372736, 745472, 1025024, 1025024, 768768, 439296, 192192, 64064, 16016, 2912, 364, 28, 1)
sage: P = polytopes.hypercube(16, backend='field')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 28 s, sys: 23.3 ms, total: 28 s
Wall time: 28 s
(1, 65536, 524288, 1966080, 4587520, 7454720, 8945664, 8200192, 5857280, 3294720, 1464320, 512512, 139776, 29120, 4480, 480, 32, 1)
}}}" enhancement closed major sage-9.3 geometry fixed face iterator, simple, simplicial, polytopes jipilab gh-LaisRast tscrim Jonathan Kliem Travis Scrimshaw N/A 63b7bd60cfc649e3d4448f970295eb7b7a977adf 63b7bd60cfc649e3d4448f970295eb7b7a977adf #29676, #29681, #30428, #30429, #30458