Opened 2 years ago

Closed 2 years ago

# Improvement for incidence matrix of polyhedra

Reported by: Owned by: gh-kliem major sage-9.2 geometry polyhedra, incidence matrix jipilab, gh-LaisRast Jonathan Kliem Travis Scrimshaw N/A 955f12b 955f12baa3ecf69aac9e7c6fb7773993f3eb9e80 #29838, #29839

This ticket collects some improvements for obtaining incidence matrices:

• The method `self._is_zero` is called many times and we can save plenty of time by obtaining it beforehand.
• We can obtain the slack matrix by multiplying the Vrepresentation matrix with the homogenous Vrepresentation. From this we can obtain the incidence matrix (strangely this last step takes up most of the time).

Unfortunately, matrix multiplication for algebraic fields isn't very efficient. So we need to keep the old method in this case.

Before this ticket:

```sage: P = polytopes.permutahedron(7)
sage: %time _ = P.incidence_matrix()
CPU times: user 751 ms, sys: 7.95 ms, total: 759 ms
Wall time: 758 ms
sage: P = polytopes.associahedron(['A', 9])
sage: %time _ = P.incidence_matrix()
CPU times: user 1.94 s, sys: 4.03 ms, total: 1.94 s
Wall time: 1.94 s
sage: P = polytopes.hypercube(14)
sage: %time _ = P.incidence_matrix()
CPU times: user 670 ms, sys: 0 ns, total: 670 ms
Wall time: 669 ms
sage: P = polytopes.permutahedron(7).dilation(sqrt2)
sage: %time _ = P.incidence_matrix()
CPU times: user 3.82 s, sys: 0 ns, total: 3.82 s
Wall time: 3.82 s
```

With this ticket:

```sage: P = polytopes.permutahedron(7)
sage: %time _ = P.incidence_matrix()
CPU times: user 64.4 ms, sys: 7 µs, total: 64.4 ms
Wall time: 63.6 ms
sage: P = polytopes.associahedron(['A', 9])
sage: %time _ = P.incidence_matrix()
CPU times: user 325 ms, sys: 12.1 ms, total: 337 ms
Wall time: 335 ms
sage: P = polytopes.hypercube(14)
sage: %time _ = P.incidence_matrix()
CPU times: user 139 ms, sys: 12 ms, total: 151 ms
Wall time: 149 ms
sage: P = polytopes.permutahedron(7).dilation(sqrt2)
sage: %time _ = P.incidence_matrix()
CPU times: user 3.69 s, sys: 3.69 ms, total: 3.69 s
Wall time: 3.69 s
```

### comment:1 Changed 2 years ago by gh-kliem

• Branch set to public/29837
• Commit set to 6dbe5d24132b62c38a1e77c09a471510d9ab1776
• Status changed from new to needs_review
• Type changed from PLEASE CHANGE to enhancement

New commits:

 ​42b5c42 `determine is_zero beforehand` ​02a8a2f `small fix` ​6dbe5d2 `use matrix multiplication to obtain incidence matrix`

### comment:2 Changed 2 years ago by gh-kliem

• Dependencies set to #29838
• Status changed from needs_review to needs_work

This should be rebased on #29838 and another ticket that speeds up getting the incidence matrix from the slack matrix.

### comment:3 Changed 2 years ago by gh-kliem

• Dependencies changed from #29838 to #29838, #29839

### comment:4 Changed 2 years ago by gh-kliem

• Dependencies changed from #29838, #29839 to #29838, #29839, #29840

### comment:5 Changed 2 years ago by gh-kliem

• Description modified (diff)

### comment:6 Changed 2 years ago by gh-kliem

• Branch changed from public/29837 to public/29837-reb
• Commit changed from 6dbe5d24132b62c38a1e77c09a471510d9ab1776 to 89aeab39856360ffe80a8e62a0e4886aa3d8d622
• Description modified (diff)
• Status changed from needs_work to needs_review

New commits:

 ​43e6dfb `implement _zero_matrix` ​05eba1e `fix bug` ​7b70830 `rename` ​47a19c6 `implement slack matrix` ​54755d7 `Merge branch 'public/29838' of git://trac.sagemath.org/sage into public/29837-reb` ​a4576d6 `set up incidence/adjacency matrix with GF(2)` ​30c4715 `Merge branch 'public/29840' of git://trac.sagemath.org/sage into public/29837-reb` ​fcd62d2 `determine is_zero beforehand` ​13b8583 `small fix` ​89aeab3 `obtain incidence matrix from slack matrix`

### comment:7 follow-up: ↓ 8 Changed 2 years ago by mkoeppe

I don't think changing the interface so that GF(2) matrices are returned is a good idea. How about leaving it as ZZ by default, and using a keyword argument for the base ring so it can be overridden.

### comment:8 in reply to: ↑ 7 Changed 2 years ago by gh-kliem

I don't think changing the interface so that GF(2) matrices are returned is a good idea. How about leaving it as ZZ by default, and using a keyword argument for the base ring so it can be overridden.

I don't think the change to `GF(2)` was needed to make things better. So I can rewrite some stuff and remove #29839, that would also do it, I think. `sage.matrix.matrix_integer_dense` is probably just as fast or faster than the other one.

I really only thought that this is the more natural thing for a 0/1 matrix. If the more natural thing is base ring integer or `GF(2)` really performs awful, I can just revert that decision.

### comment:9 Changed 2 years ago by mkoeppe

See my comment in #29840

### comment:10 Changed 2 years ago by gh-kliem

• Dependencies changed from #29838, #29839, #29840 to #29838, #29839
• Status changed from needs_review to needs_work

Changing the base ring of incidence matrices was rejected in #29340.

### comment:11 follow-up: ↓ 12 Changed 2 years ago by dimpase

I wish this was implemented using numpy matrices (knows as arrays), which provide faster linear algebra and have built-in methods to manipulate zero patterns of their matrices.

### comment:12 in reply to: ↑ 11 Changed 2 years ago by gh-kliem

I don't know how fast conversion back and forth works. It is true, that numpy is a bit faster, but that doesn't help me if I cannot convert things.

E.g.

```sage: P = polytopes.associahedron(['A', 9])
sage: %time a = np.array(P.Vrepresentation())
CPU times: user 383 ms, sys: 0 ns, total: 383 ms
Wall time: 382 ms
```

This is already longer than it takes to obtain the entire incidence matrix. Of course this is most likely not an ideal way to convert, but I don't know any better way at the moment.

And conversion back is also slow.

I wish this was implemented using numpy matrices (knows as arrays), which provide faster linear algebra and have built-in methods to manipulate zero patterns of their matrices.

### comment:13 Changed 2 years ago by gh-kliem

• Branch changed from public/29837-reb to public/29837-reb2
• Commit changed from 89aeab39856360ffe80a8e62a0e4886aa3d8d622 to 3d28d09c5c74cdc8cb79f3b17ef50b1bff8b828d
• Status changed from needs_work to needs_review

New commits:

 ​62f1ff9 `use integer matrix for zero_pattern_matrix` ​88f6025 `Merge branch 'public/29838' of git://trac.sagemath.org/sage into public/29837-reb2` ​7cee020 `determine is_zero beforehand` ​3d28d09 `small fix`

### comment:14 Changed 2 years ago by git

• Commit changed from 3d28d09c5c74cdc8cb79f3b17ef50b1bff8b828d to 7ef6a111bf70637a01b6789819b87dde647bdc4c

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

 ​7ef6a11 `use slack matrix to obtain incidence matrix quicker`

### comment:15 Changed 2 years ago by git

• Commit changed from 7ef6a111bf70637a01b6789819b87dde647bdc4c to 759d1f20427b7a213789e1c114e427824f0884c2

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

 ​b583745 `make methods more generic` ​535dc85 `note for developers` ​0988730 `Merge branch 'public/29839' of git://trac.sagemath.org/sage into public/29837-reb2` ​759d1f2 `account for change in #29839`

### comment:16 Changed 2 years ago by gh-kliem

• Branch changed from public/29837-reb2 to public/29837-reb3
• Commit changed from 759d1f20427b7a213789e1c114e427824f0884c2 to 764a99b9a8c476f1d73e120f90b68652ff230eae

Last 10 new commits:

 ​9462376 `Adding optimized get_is_zero_unsafe() to rational sparse matrices.` ​94febde `Custom get_is_zero_unsafe() for modn sparse matrices.` ​bf0352f `See if we can check trivial zeros first for symbolic matrices.` ​2a08abe `small mistakes` ​333c4ba `wrong doctest` ​82c6b4a `docstring` ​211f4f1 `Merge branch 'public/29839' of git://trac.sagemath.org/sage into public/29837-reb3` ​4c5433e `determine is_zero beforehand` ​27a1b90 `use slack matrix to obtain incidence matrix quicker` ​764a99b `account for change in #29839`

### comment:17 Changed 2 years ago by gh-kliem

Needs review.

The the ticket itself is only 3 commits on top of #29838 and #29839, which are both closed now.

### comment:18 Changed 2 years ago by gh-kliem

• Description modified (diff)

### comment:19 Changed 2 years ago by tscrim

You might be able to get a little more speed out by doing

```-return x == 0
+return (not x)
```

### comment:20 Changed 2 years ago by tscrim

• Reviewers set to Travis Scrimshaw

However, whether you make that change or not, you can set a positive review on my behalf.

### comment:21 Changed 2 years ago by gh-kliem

About three percent for `P = polytopes.permutahedron(7).dilation(sqrt2)`.

Thank you.

### comment:22 Changed 2 years ago by git

• Commit changed from 764a99b9a8c476f1d73e120f90b68652ff230eae to f70e1c5d22c28afd9d3145ce43f26a4eb8b98504

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

 ​f70e1c5 `improvement suggested by reviewer`

### comment:23 Changed 2 years ago by gh-kliem

• Status changed from needs_review to positive_review

### comment:24 Changed 2 years ago by fbissey

I am getting this with this ticket in sage-on-gentoo

```sage -t --long --warn-long 101.0 /usr/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_cdd.py
**********************************************************************
File "/usr/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_cdd.py", line 508, in sage.geometry.polyhedron.backend_cdd.Polyhedron_RDF_cdd.__init__
Failed example:
TestSuite(p).run()
Expected nothing
Got:
Failure in _test_an_affine_basis:
Traceback (most recent call last):
File "/usr/lib/python3.7/site-packages/sage/misc/sage_unittest.py", line 296, in run
test_method(tester=tester)
File "/usr/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 2122, in _test_an_affine_basis
b = self.an_affine_basis()
File "/usr/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 2085, in an_affine_basis
chain = self.a_maximal_chain()[1:]  # we exclude the empty face
File "/usr/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 3098, in a_maximal_chain
comb_chain = self.combinatorial_polyhedron().a_maximal_chain()
File "sage/misc/cachefunc.pyx", line 2310, in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/build/cythonized/sage/misc/cachefunc.c:12875)
self.cache = f(self._instance)
File "/usr/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 3362, in combinatorial_polyhedron
return CombinatorialPolyhedron(self)
File "sage/geometry/polyhedron/combinatorial_polyhedron/base.pyx", line 367, in sage.geometry.polyhedron.combinatorial_polyhedron.base.CombinatorialPolyhedron.__init__ (/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/build/cythonized/sage/geometry/polyhedron/combinatorial_polyhedron/base.c:6786)
data = data.incidence_matrix()
File "sage/misc/cachefunc.pyx", line 2310, in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python3_7/build/cythonized/sage/misc/cachefunc.c:12875)
self.cache = f(self._instance)
File "/usr/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 2749, in incidence_matrix
is_zero == self._is_zero
UnboundLocalError: local variable 'is_zero' referenced before assignment
------------------------------------------------------------
The following tests failed: _test_an_affine_basis
**********************************************************************
```

seems circular.

### comment:25 Changed 2 years ago by tscrim

• Status changed from positive_review to needs_work
```-is_zero == self._is_zero
+is_zero = self._is_zero
```

### comment:26 Changed 2 years ago by gh-kliem

The problem is that usually the cdd backend figures out the incidence matrix itself for inexact polyhedra. So you don't notice, because `incidence_matrix` is never run (except for the empty polyhedron, hence the error). I should add a doctest for this.

Last edited 2 years ago by gh-kliem (previous) (diff)

### comment:27 Changed 2 years ago by gh-kliem

• Branch changed from public/29837-reb3 to public/29837-reb4
• Commit changed from f70e1c5d22c28afd9d3145ce43f26a4eb8b98504 to da9ec61583cd63e246b8bbd326c3958f4679d12d
• Status changed from needs_work to needs_review

I rebased as well.

New commits:

 ​169077a `Merge branch 'public/29837-reb3' of git://trac.sagemath.org/sage into public/29837-reb4` ​26590f1 `fix mistake` ​da9ec61 `add doctest`

### comment:28 follow-up: ↓ 30 Changed 2 years ago by tscrim

Trivial tweak, but the formatting is better:

```         Test that this method works for inexact base ring
-        (`cdd` sets the cache already)::
+        (``cdd`` sets the cache already)::
```

### comment:29 Changed 2 years ago by git

• Commit changed from da9ec61583cd63e246b8bbd326c3958f4679d12d to 955f12baa3ecf69aac9e7c6fb7773993f3eb9e80

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

 ​955f12b `sphinx syntax`

### comment:30 in reply to: ↑ 28 Changed 2 years ago by gh-kliem

Done.

Trivial tweak, but the formatting is better:

```         Test that this method works for inexact base ring
-        (`cdd` sets the cache already)::
+        (``cdd`` sets the cache already)::
```

### comment:31 Changed 2 years ago by tscrim

• Status changed from needs_review to positive_review

Thanks.

### comment:32 Changed 2 years ago by vbraun

• Branch changed from public/29837-reb4 to 955f12baa3ecf69aac9e7c6fb7773993f3eb9e80
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.