Improve face iterator for simple/simplicial polytopes #30040

kliem · 2020-07-01T15:05:26Z

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)

Depends on #29676
Depends on #29681
Depends on #30428
Depends on #30429
Depends on #30458

CC: @jplab @LaisRast @tscrim

Component: geometry

Keywords: face iterator, simple, simplicial, polytopes

Author: Jonathan Kliem

Branch/Commit: 63b7bd6

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/30040

The text was updated successfully, but these errors were encountered:

kliem · 2020-07-01T15:06:18Z

New commits:

`0c44221`	`important attributes of iterator in structure`
`efb0bd3`	`src/simplification of doctests`
`53fd2a2`	`fixed failing doctest`
`142d3a8`	`bad alignment causing bug noticed in #28982`
`2b07f03`	`Merge branch 'public/28894-reb5' of git://trac.sagemath.org/sage into develop`
`33804bd`	`prepare slightly modified algorithm for simple/simplicial polytopes`
`99579b3`	`faster algorithm for simple/simplicial polytopes`
`46d1eb6`	`small fixes`
`ceab503`	`improvements in documentation`

kliem · 2020-07-01T15:06:18Z

Branch: public/30040

kliem · 2020-07-01T15:06:18Z

Commit: ceab503

kliem · 2020-08-21T11:12:41Z

comment:4

Needs rebase.

kliem · 2020-08-24T09:48:09Z

Changed dependencies from #28894 to #30428

kliem · 2020-08-24T09:50:55Z

Changed dependencies from #30428 to #30428, #30429

kliem · 2020-08-24T10:05:04Z

Changed work issues from There is a merge conflict with #29676. Whichever takes longer needs to be rebased. to There are merge conflicts with #29676, #29681. Whichever takes longer needs to be rebased.

kliem · 2020-08-24T10:46:41Z

Changed branch from public/30040 to public/30040-reb

kliem · 2020-08-24T10:46:41Z

Changed commit from ceab503 to 7ffac00

kliem · 2020-08-24T10:46:41Z

New commits:

`39f3a38`	`directly check is_simple/is_simplicial`
`fe880a4`	input of `intersection` in standard order
`bc27cd1`	`Merge branch 'public/30429' of git://trac.sagemath.org/sage into public/30040`
`4478f3c`	`unite and is_zero for bit_vectors`
`131c065`	add a specialized `get_next_level_simple`
`bc00d42`	`prepare slightly modified algorithm for simple/simplicial polytopes`
`4fdc787`	`faster algorithm for simple/simplicial polytopes`
`4724d3c`	`small fixes`
`0297853`	`improvements in documentation`
`7ffac00`	`changes in 30429`

tscrim · 2020-08-25T00:58:30Z

comment:11

Typo: intervalls -> intervals

Bikeshedding: Personally, I find sizeof(uint64_t **) confusing compared to sizeof(uint64_t**), where IMO is more indicative that it is a pointer. Feel free to ignore this comment.

I feel like #29676 and #29681 are more natural as dependencies of this ticket given their changes, but that is not a strong opinion. I am happy to do the review of those tickets as well. Also, beyond these to things above, this ticket LGTM.

sagetrac-git · 2020-08-25T06:32:56Z

Changed commit from 7ffac00 to 01b4154

sagetrac-git · 2020-08-25T06:32:56Z

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

`01b4154`	`typo`

kliem · 2020-08-25T06:48:57Z

comment:13

At some point I started doing it like cdef uint64_t *foo, hence the sizeof(uint64_t *).

This works well, because you can legally do cdef uint64_t *foo, *foo2, however I quickly stopped that because I got warnings that I'm not supposed to do this.

Once you start declaring each pointer in its own line, you can go to cdef uint64_t* foo, which is more natural, I agree. I just didn't yet. I think I should have a seperate ticket that gets this stuff in order in the entire folder. At the moment everything is one style, which is also desirable, I think.
In principal Make a nogil version of the most important methods of FaceIterator. #29676 and Small improvements for FaceIterator_base #29681 are more natural as dependencies of this ticket than vice versa (both are somewhat nice to review at the moment). I agree. But I don't want them to be in the way (in case they are sitting there without review). I'm happy to rebase whatever makes sense

kliem · 2020-08-25T13:16:57Z

comment:14

Actually, there is a mistake.

To use the coatom representation to a mark a face as visited will work for polyhedra, but does require the uniqueness of the coatom representation. So this will not work for simplicial complexes.

kliem · 2020-08-25T13:33:20Z

comment:15

Never mind. I should have read closely and rethought. The atom-representation is not unique. This is the entire point of worrying about the coatom representation. It's not because it is shorter, but because this is the only thing that will work for simplicial complexes.

kliem · 2020-09-02T06:11:18Z

comment:25

merge conflict

sagetrac-git · 2020-09-02T06:14:20Z

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

`40e6667`	`Merge branch 'u/gh-kliem/improved_count_atoms' of git://trac.sagemath.org/sage into public/30040-reb2`

sagetrac-git · 2020-09-02T06:14:20Z

Changed commit from ed6e966 to 40e6667

sagetrac-git · 2020-09-02T06:21:13Z

Changed commit from 40e6667 to 242cba7

sagetrac-git · 2020-09-02T06:21:13Z

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

`242cba7`	`Merge branch 'develop' of git://trac.sagemath.org/sage into public/30040-reb2`

kliem · 2020-09-02T06:34:56Z

comment:28

Tests still pass. It really appears to be a question in what order you merge.

sagetrac-git · 2020-09-09T08:05:06Z

Changed commit from 242cba7 to 63b7bd6

sagetrac-git · 2020-09-09T08:05:06Z

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

`5311cdf`	`grammar`
`eef6cf5`	`unite and is_zero for bit_vectors`
`a4fa8cf`	add a specialized `get_next_level_simple`
`07b9746`	`changes in 30429`
`c51fe62`	simplify `get_next_level_simple by 30458
`f3e2ddc`	`prepare slightly modified algorithm for simple/simplicial polytopes`
`edad681`	`typo`
`5939b5d`	`faster algorithm for simple/simplicial polytopes`
`f997cec`	`small fixes`
`63b7bd6`	`improvements in documentation`

kliem · 2020-09-09T08:05:25Z

comment:30

Rebased.

vbraun · 2020-11-15T22:47:36Z

Changed branch from public/30040-reb2 to 63b7bd6

kliem added this to the sage-9.2 milestone Jul 1, 2020

kliem added p: major / 3 labels Jul 1, 2020

kliem added s: needs review labels Jul 1, 2020

kliem added s: needs work and removed s: needs review labels Aug 21, 2020

This comment has been minimized.

Sign in to view

kliem added s: needs review and removed s: needs work labels Aug 24, 2020

kliem added s: needs work and removed s: needs review labels Aug 25, 2020

kliem removed the s: needs work label Aug 25, 2020

kliem added s: needs work and removed s: positive review labels Sep 2, 2020

kliem added s: positive review and removed s: needs work labels Sep 2, 2020

sagetrac-git mannequin added s: needs review and removed s: positive review labels Sep 9, 2020

kliem added s: positive review and removed s: needs review labels Sep 9, 2020

mkoeppe modified the milestones: sage-9.2, sage-9.3 Oct 24, 2020

vbraun removed the s: positive review label Nov 15, 2020

vbraun closed this as completed in 7e1fdf7 Nov 15, 2020

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Improve face iterator for simple/simplicial polytopes #30040

Improve face iterator for simple/simplicial polytopes #30040

kliem commented Jul 1, 2020

kliem commented Jul 1, 2020

kliem commented Jul 1, 2020

kliem commented Jul 1, 2020

kliem commented Aug 21, 2020

This comment has been minimized.

This comment has been minimized.

kliem commented Aug 24, 2020

kliem commented Aug 24, 2020

kliem commented Aug 24, 2020

kliem commented Aug 24, 2020

kliem commented Aug 24, 2020

kliem commented Aug 24, 2020

tscrim commented Aug 25, 2020

sagetrac-git mannequin commented Aug 25, 2020

sagetrac-git mannequin commented Aug 25, 2020

kliem commented Aug 25, 2020

kliem commented Aug 25, 2020

kliem commented Aug 25, 2020

kliem commented Sep 2, 2020

sagetrac-git mannequin commented Sep 2, 2020

sagetrac-git mannequin commented Sep 2, 2020

sagetrac-git mannequin commented Sep 2, 2020

sagetrac-git mannequin commented Sep 2, 2020

kliem commented Sep 2, 2020

sagetrac-git mannequin commented Sep 9, 2020

sagetrac-git mannequin commented Sep 9, 2020

kliem commented Sep 9, 2020

vbraun commented Nov 15, 2020

Improve face iterator for simple/simplicial polytopes #30040

Improve face iterator for simple/simplicial polytopes #30040

Comments

kliem commented Jul 1, 2020

kliem commented Jul 1, 2020

kliem commented Jul 1, 2020

kliem commented Jul 1, 2020

kliem commented Aug 21, 2020

This comment has been minimized.

This comment has been minimized.

kliem commented Aug 24, 2020

kliem commented Aug 24, 2020

kliem commented Aug 24, 2020

kliem commented Aug 24, 2020

kliem commented Aug 24, 2020

kliem commented Aug 24, 2020

tscrim commented Aug 25, 2020

sagetrac-git mannequin commented Aug 25, 2020

sagetrac-git mannequin commented Aug 25, 2020

kliem commented Aug 25, 2020

kliem commented Aug 25, 2020

kliem commented Aug 25, 2020

kliem commented Sep 2, 2020

sagetrac-git mannequin commented Sep 2, 2020

sagetrac-git mannequin commented Sep 2, 2020

sagetrac-git mannequin commented Sep 2, 2020

sagetrac-git mannequin commented Sep 2, 2020

kliem commented Sep 2, 2020

sagetrac-git mannequin commented Sep 9, 2020

sagetrac-git mannequin commented Sep 9, 2020

kliem commented Sep 9, 2020

vbraun commented Nov 15, 2020