id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
31262 Implement non zero chunks for sparse bitsets gh-kliem "For very large and challenging computations, most of the elements of the face lattice contain rather few atoms/bits. With little changes to the code, we can just collect the non zero chunks (64,128 or 256 bits).
RoaringBitmap performs better (starting with maybe 100,000 bits, but not with less, as container contain 64k bits), but that would add an extra dependency and make things more complicated.
To avoid code duplications, we also gather some functions in `bitset_intrinsics.h` that work just the same (e.g. intersection and union).
(This actually accounts for most changes by this ticket.)
Before (on #27103):
{{{
sage: P = polytopes.Birkhoff_polytope(5)
sage: C = CombinatorialPolyhedron(P)
sage: %time _ = C.f_vector()
CPU times: user 468 ms, sys: 0 ns, total: 468 ms
Wall time: 467 ms
sage: P = polytopes.Birkhoff_polytope(5)
sage: C = CombinatorialPolyhedron(P)
sage: %time _ = C.f_vector()
CPU times: user 440 ms, sys: 0 ns, total: 440 ms
Wall time: 439 ms
sage: P = polytopes.hypercube(14)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time _ = C.f_vector()
CPU times: user 5.13 s, sys: 4.03 ms, total: 5.14 s
Wall time: 5.13 s
sage: P = polytopes.hypercube(15)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time _ = C.f_vector()
CPU times: user 30 s, sys: 32 ms, total: 30 s
Wall time: 30 s
sage: P = polytopes.permutahedron(6)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time _ = C.f_vector()
CPU times: user 1.68 ms, sys: 6 µs, total: 1.68 ms
Wall time: 1.69 ms
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 89.1 ms, sys: 4 µs, total: 89.1 ms
Wall time: 88.9 ms
sage: P = polytopes.permutahedron(8, backend='normaliz')
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time _ = C.f_vector()
CPU times: user 14.2 s, sys: 8 ms, total: 14.2 s
Wall time: 14.2 s
sage: P = polytopes.associahedron(['A', 11], backend='normaliz')
sage: C = CombinatorialPolyhedron(P)
sage: %time _ = C.f_vector()
CPU times: user 24.3 s, sys: 8.01 ms, total: 24.3 s
Wall time: 24.3 s
}}}
After:
{{{
# Slight slowdown for few atoms.
sage: P = polytopes.Birkhoff_polytope(5)
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 475 ms, sys: 0 ns, total: 475 ms
Wall time: 474 ms
(1, 120, 5040, 50250, 233400, 631700, 1113700, 1367040, 1220550, 817150, 419225, 167200, 52120, 12600, 2300, 300, 25, 1)
sage: P = polytopes.hypercube(14)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 1.67 s, sys: 0 ns, total: 1.67 s
Wall time: 1.66 s
(1, 16385, 131069, 487383, 1117948, 1769482, 2047331, 1788501, 1200342, 622908, 248963, 75361, 16640, 2470, 197, 1)
sage: P = polytopes.hypercube(15)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 7.28 s, sys: 8 ms, total: 7.28 s
Wall time: 7.28 s
(1, 32769, 278525, 1105876, 2723539, 4657926, 5866861, 5629624, 4196907, 2454738, 1128127, 404404, 110929, 22386, 3059, 226, 1)
sage: P = polytopes.permutahedron(6)
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 1.44 ms, sys: 79 µs, total: 1.52 ms
Wall time: 1.52 ms
(1, 721, 1987, 1956, 808, 120, 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 20.8 ms, sys: 0 ns, total: 20.8 ms
Wall time: 20.9 ms
(1, 5041, 16251, 19761, 11144, 2860, 267, 1)
sage: P = polytopes.permutahedron(8, backend='normaliz')
sage: P1 = P.stack(next(P.face_generator(1)))
sage: C = CombinatorialPolyhedron(P1)
sage: %time C.f_vector()
CPU times: user 616 ms, sys: 8 ms, total: 624 ms
Wall time: 623 ms
(1, 40321, 148899, 215690, 154215, 56022, 9489, 572, 1)
# No change for simplicial/simple polytopes.
sage: P = polytopes.associahedron(['A', 11], backend='normaliz')
sage: C = CombinatorialPolyhedron(P)
sage: %time C.f_vector()
CPU times: user 24.3 s, sys: 16.3 ms, total: 24.3 s
Wall time: 24.3 s
(1, 208012, 1144066, 2735810, 3730650, 3197700, 1790712, 659736, 157080, 23100, 1925, 77, 1)
}}}
This is the last subsequent improvement in comparison to sage 8.9 mentioned in https://arxiv.org/abs/1905.01945.
Follow ups:
- Move things from `geometry/polyhedron/combinatorial_polyhedron` to a more general location.
- Some renamings for lattices in general `face` -> `element`.
- Expose to simplical complexes.
- Expose to lattice of flats of matroids." enhancement closed major sage-9.3 geometry fixed combinatorial polyhedron, sparse bitsets stumpc5 tscrim Jonathan Kliem Travis Scrimshaw N/A b3212d0bb74109461114b23d63fc26e604c121f2 b3212d0bb74109461114b23d63fc26e604c121f2 #27103