Implement `zero_pattern_matrix` #29839

kliem · 2020-06-10T13:12:29Z

We implement a method on matrices that gives a new matrix with specified base ring
and entries 1 where and only where the initial matrix had zero entries, and 0 elsewhere.

Motivation: This method is useful to obtain the incidence matrix of a polyhedron from the slack matrix in #29837.

Along the way this ticket also fixes a bug:

M = Matrix(ZZ, [[0,1],[0,1]])
sage: M._mod_int(2).transpose()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-8587f9dc80b2> in <module>()
----> 1 M._mod_int(Integer(2)).transpose()

/srv/public/kliem/sage/local/lib/python3.7/site-packages/sage/matrix/matrix_mod2_dense.pyx in sage.matrix.matrix_mod2_dense.Matrix_mod2_dense.transpose (build/cythonized/sage/matrix/matrix_mod2_dense.c:10873)()
   1400             1
   1401         """
-> 1402         cdef Matrix_mod2_dense A = self.new_matrix(ncols = self._nrows,  nrows = self._ncols)
   1403         if self._nrows == 0 or self._ncols == 0:
   1404             return A

TypeError: Cannot convert sage.matrix.matrix_modn_dense_float.Matrix_modn_dense_float to sage.matrix.matrix_mod2_dense.Matrix_mod2_dense

To optimize this method, a matrix class can use the optimized get_is_zero_unsafe.
In this ticket this is done for most matrix classes. We also use this new optimized zero check in places where it makes sense.

Component: basic arithmetic

Keywords: incidence matrix, zero pattern

Author: Jonathan Kliem, Travis Scrimshaw

Branch/Commit: 82c6b4a

Reviewer: Travis Scrimshaw, Jonathan Kliem

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

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

kliem · 2020-06-10T13:13:34Z

comment:1

Better suggestions for a name would be welcome. _zero_matrix is somewhat strange.

kliem · 2020-06-10T13:13:56Z

Branch: public/29839

kliem · 2020-06-10T13:13:56Z

Commit: 43e6dfb

kliem · 2020-06-10T13:13:56Z

New commits:

`43e6dfb`	`implement _zero_matrix`

dimpase · 2020-06-10T13:57:34Z

comment:3

zero_pattern_matrix?

kliem · 2020-06-10T14:00:15Z

comment:4

Better anyway. With public or semiprivate? (leading underscore).

Btw, there is a bug here. I copied this from _mod_two which apparently sets up the parent incorrect:

M = Matrix(ZZ, [[0,1],[0,1]])
sage: M._mod_int(2).transpose()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-8587f9dc80b2> in <module>()
----> 1 M._mod_int(Integer(2)).transpose()

/srv/public/kliem/sage/local/lib/python3.7/site-packages/sage/matrix/matrix_mod2_dense.pyx in sage.matrix.matrix_mod2_dense.Matrix_mod2_dense.transpose (build/cythonized/sage/matrix/matrix_mod2_dense.c:10873)()
   1400             1
   1401         """
-> 1402         cdef Matrix_mod2_dense A = self.new_matrix(ncols = self._nrows,  nrows = self._ncols)
   1403         if self._nrows == 0 or self._ncols == 0:
   1404             return A

TypeError: Cannot convert sage.matrix.matrix_modn_dense_float.Matrix_modn_dense_float to sage.matrix.matrix_mod2_dense.Matrix_mod2_dense
sage:  MS = matrix_space.MatrixSpace(IntegerModRing(2), self._nrows, self._ncols)

dimpase · 2020-06-10T14:01:51Z

comment:5

shouldn't def _zero_matrix(self): (or rather named as in comment:3) be cpdef, to facilitate calling from Cython?

dimpase · 2020-06-10T14:05:07Z

comment:6

Replying to @kliem:

Better anyway. With public or semiprivate? (leading underscore).

Btw, there is a bug here. I copied this from _mod_two which apparently sets up the parent incorrect:

M = Matrix(ZZ, [[0,1],[0,1]])
sage: M._mod_int(2).transpose()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-8587f9dc80b2> in <module>()
----> 1 M._mod_int(Integer(2)).transpose()

/srv/public/kliem/sage/local/lib/python3.7/site-packages/sage/matrix/matrix_mod2_dense.pyx in sage.matrix.matrix_mod2_dense.Matrix_mod2_dense.transpose (build/cythonized/sage/matrix/matrix_mod2_dense.c:10873)()
   1400             1
   1401         """
-> 1402         cdef Matrix_mod2_dense A = self.new_matrix(ncols = self._nrows,  nrows = self._ncols)
   1403         if self._nrows == 0 or self._ncols == 0:
   1404             return A

TypeError: Cannot convert sage.matrix.matrix_modn_dense_float.Matrix_modn_dense_float to sage.matrix.matrix_mod2_dense.Matrix_mod2_dense
sage:  MS = matrix_space.MatrixSpace(IntegerModRing(2), self._nrows, self._ncols)

why can't you use mod?

sage: M = Matrix(ZZ, [[0,1],[0,1]])
sage: M.mod(2)
[0 1]
[0 1]

kliem · 2020-06-10T14:34:41Z

comment:7

Because it is slow. I just copied the construction of the parent from _mod_two.
I really don't know why, but change_ring is really slow (e.g. for ZZ -> GF(2)). It should be improved, but maybe not in this ticket.

_mod_two uses the ring with two elements to obtain the parent. However, get_matrix_class gives you modn in this case. It gives you mod2 if you pass the field with two elements.

kliem · 2020-06-10T14:35:18Z

comment:8

And M.mod is really not what I want. I just illustrated this bug.

kliem · 2020-06-10T14:44:43Z

Changed keywords from incidence matrix, zero entries to incidence matrix, zero pattern

sagetrac-git · 2020-06-10T14:47:35Z

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

`05eba1e`	`fix bug`
`7b70830`	`rename`

sagetrac-git · 2020-06-10T14:47:35Z

Changed commit from 43e6dfb to 7b70830

kliem · 2020-06-10T14:47:48Z

New commits:

`05eba1e`	`fix bug`
`7b70830`	`rename`

kliem · 2020-06-10T20:05:00Z

comment:12

I really want a new integer matrix.

sagetrac-git · 2020-06-10T22:36:55Z

Changed commit from 7b70830 to 62f1ff9

sagetrac-git · 2020-06-10T22:36:55Z

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

`62f1ff9`	`use integer matrix for zero_pattern_matrix`

tscrim · 2020-06-10T22:43:11Z

comment:15

Have you tried doing either x = 1 - x or x = not x? These should be fast as they avoid intermediate function calls and the first should work for any ring (maybe replace 1 with one where one = self.base_ring().one()).

sagetrac-git · 2020-06-13T01:59:30Z

Changed commit from 169fa6c to 9462376

sagetrac-git · 2020-06-13T01:59:30Z

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

`4257c79`	`Adding get_is_zero_unsafe() for generic sparse matrices.`
`78ca753`	`Adding a custom get_is_zero_unsafe for sparse integer matrices.`
`9462376`	`Adding optimized get_is_zero_unsafe() to rational sparse matrices.`

sagetrac-git · 2020-06-13T02:05:26Z

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

`94febde`	`Custom get_is_zero_unsafe() for modn sparse matrices.`

sagetrac-git · 2020-06-13T02:05:26Z

Changed commit from 9462376 to 94febde

sagetrac-git · 2020-06-13T02:23:20Z

Changed commit from 94febde to bf0352f

sagetrac-git · 2020-06-13T02:23:20Z

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

`bf0352f`	`See if we can check trivial zeros first for symbolic matrices.`

tscrim · 2020-06-13T02:25:35Z

comment:39

Okay, that takes care of the sparse matrices and symbolic matrices.

Slightly surprisingly, the gap matrices don't benefit from not going through Sage (well, at least for integer matrices).

I am done now.

sagetrac-git · 2020-06-13T09:38:17Z

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

`2a08abe`	`small mistakes`

sagetrac-git · 2020-06-13T09:38:17Z

Changed commit from bf0352f to 2a08abe

kliem · 2020-06-13T09:39:14Z

comment:41

IMO this is good now. The doctests should also pass.

kliem · 2020-06-13T09:39:14Z

Changed reviewer from Travis Scrimshaw to Travis Scrimshaw, Jonathan Kliem

sagetrac-git · 2020-06-13T19:01:55Z

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

`333c4ba`	`wrong doctest`

sagetrac-git · 2020-06-13T19:01:55Z

Changed commit from 2a08abe to 333c4ba

tscrim · 2020-06-13T22:39:20Z

comment:43

Thank you. Two more little things:

         INPUT:
 
-        - `ring` -- (optional); base ring of the output; default is `ZZ`
+        - `ring` -- (optional); base ring of the output; default is ``ZZ``

and we should add a test for the empty row/column and empty matrix for Matrix_gf2e_dense.__bool__ (as that was a good catch). I can do this tomorrow.

sagetrac-git · 2020-06-13T23:03:38Z

Changed commit from 333c4ba to 82c6b4a

sagetrac-git · 2020-06-13T23:03:38Z

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

`82c6b4a`	`docstring`

kliem · 2020-06-13T23:05:00Z

comment:45

Replying to @tscrim:

and we should add a test for the empty row/column and empty matrix for Matrix_gf2e_dense.__bool__ (as that was a good catch).

Well the bot was segfaulting (and me to, when running the test).

tscrim · 2020-06-13T23:46:00Z

comment:46

Okay, then positive review. Thank you.

kliem · 2020-06-14T08:34:57Z

comment:47

I like that you made a polyhedron only ticket, into a more general improvement for other parts as well.

slel · 2020-06-18T02:09:57Z

comment:48

(Slightly amending ticket description, please check that works for you.).

vbraun · 2020-06-27T09:25:22Z

Changed branch from public/29839 to 82c6b4a

kliem added this to the sage-9.2 milestone Jun 10, 2020

kliem added c: basic arithmetic labels Jun 10, 2020

kliem added the s: needs review label Jun 10, 2020

This comment has been minimized.

Sign in to view

kliem changed the title ~~Implement _zero_matrix for dense integer and rational matrices~~ Implement zero_pattern_matrix for dense integer and rational matrices Jun 10, 2020

kliem added s: needs work and removed s: needs review labels Jun 10, 2020

This comment has been minimized.

Sign in to view

kliem added s: needs review and removed s: needs work labels Jun 10, 2020

tscrim added s: needs review and removed s: needs work labels Jun 13, 2020

This comment has been minimized.

Sign in to view

tscrim added s: positive review and removed s: needs review labels Jun 13, 2020

This comment has been minimized.

Sign in to view

vbraun removed the s: positive review label Jun 27, 2020

vbraun closed this as completed in 4f305e2 Jun 27, 2020

kliem mentioned this issue Jul 10, 2020

Improvement for incidence matrix of polyhedra #29837

Closed

Implement zero_pattern_matrix #29839

Implement zero_pattern_matrix #29839

Comments

kliem commented Jun 10, 2020

kliem commented Jun 10, 2020

kliem commented Jun 10, 2020

kliem commented Jun 10, 2020

kliem commented Jun 10, 2020

dimpase commented Jun 10, 2020

kliem commented Jun 10, 2020

dimpase commented Jun 10, 2020

dimpase commented Jun 10, 2020

kliem commented Jun 10, 2020

kliem commented Jun 10, 2020

This comment has been minimized.

kliem commented Jun 10, 2020

sagetrac-git mannequin commented Jun 10, 2020

sagetrac-git mannequin commented Jun 10, 2020

kliem commented Jun 10, 2020

kliem commented Jun 10, 2020

sagetrac-git mannequin commented Jun 10, 2020

sagetrac-git mannequin commented Jun 10, 2020

This comment has been minimized.

tscrim commented Jun 10, 2020

sagetrac-git mannequin commented Jun 13, 2020

sagetrac-git mannequin commented Jun 13, 2020

sagetrac-git mannequin commented Jun 13, 2020

sagetrac-git mannequin commented Jun 13, 2020

sagetrac-git mannequin commented Jun 13, 2020

sagetrac-git mannequin commented Jun 13, 2020

This comment has been minimized.

tscrim commented Jun 13, 2020

sagetrac-git mannequin commented Jun 13, 2020

sagetrac-git mannequin commented Jun 13, 2020

kliem commented Jun 13, 2020

kliem commented Jun 13, 2020

sagetrac-git mannequin commented Jun 13, 2020

sagetrac-git mannequin commented Jun 13, 2020

tscrim commented Jun 13, 2020

sagetrac-git mannequin commented Jun 13, 2020

sagetrac-git mannequin commented Jun 13, 2020

kliem commented Jun 13, 2020

tscrim commented Jun 13, 2020

kliem commented Jun 14, 2020

This comment has been minimized.

slel commented Jun 18, 2020

vbraun commented Jun 27, 2020

Implement `zero_pattern_matrix` #29839

Implement `zero_pattern_matrix` #29839