permanental_minor_vector, matching polynomial

[sagetrac-pernici]

Added function permanental_minor_polynomial, which computes the polynomial of the sums of the permanental minors in an efficient way, see arXiv:1406.5337.

As a benchmark, consider dancing.sage. On my computer dance(10) took 3 hours using sage-6.2; it takes 0.08 seconds with this patch, using the
Butera-Pernici algorithm, 13 seconds using the Godsil algorithm.

In the case of banded matrices, the speedup is greater, since for fixed bandwidth the new algorithm is polynomial; here is a permanent which cannot be computed with sage-6.2

sage: from sage.matrix.matrix_misc import permanental_minor_polynomial
sage: n, w = 100, 5
sage: m = matrix([[i*j + 1 if abs(i-j) <= w else 0
....:              for i in range(n)] for j in range(n)])
sage: time p = permanental_minor_polynomial(m, permanent_only=True)
Wall time: 773 ms

This can be used to compute the matching polynomial of bipartite graphs much faster than matching_polynomial for certain graphs. For example, using the attached file to compute the reduced adjacency matrix of a 2d grid (n1, n2):

sage: from grid import sq_mat
sage: from sage.matrix.matrix_misc import permanental_minor_polynomial
sage: m = matrix(sq_mat(6, 6))
sage: time a = permanental_minor_polynomial(m)
Wall time: 10.6 ms

sage: g = BipartiteGraph(m)
sage: time p = g.matching_polynomial()
Wall time: 46.9 s

For n1,n2=10,10 permanental_minor_vector(m) takes 0.3s
For n1,n2=50,6 it takes 0.5s

CC: @nathanncohen @jaapspies

Component: linear algebra

Author: Mario Pernici

Branch/Commit: 901d36c

Reviewer: Vincent Delecroix

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

[sagetrac-pernici]

Author: Mario Pernici

[sagetrac-pernici]

Branch: u/pernici/ticket/16603

[sagetrac-git]

Commit: b0d7145

[sagetrac-git]

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

b0d7145

fixed bug in `permanental_minor_vector` in case of vanishing permanent

[sagetrac-pernici]

Attachment: grid.py.gz

[fchapoton]

Changed branch from u/pernici/ticket/16603 to public/ticket/16603

[fchapoton]

Changed commit from b0d7145 to f65acde

[fchapoton]

comment:8

I have had a quick look and made a review patch. You need to document the auxiliary function.

---

New commits:

55d328f	Merge branch 'u/pernici/ticket/16603' in 6.4.rc0
f65acde	trac #16603 first review commit

[sagetrac-pernici]

Changed branch from public/ticket/16603 to u/pernici/ticket/16603

[sagetrac-pernici]

comment:10

I made a commit in which I documented the auxiliary function, but by mistake I committed it
to u/pernici/ticket/16603 instead of public/ticket/16603

---

New commits:

947ddd1

Added missing documentation in ``_prm_mul``;

[sagetrac-pernici]

Changed commit from f65acde to 947ddd1

[fchapoton]

comment:11

Do you want this to be reviewed ? If yes, please turn it into "needs review".

[sagetrac-pernici]

comment:12

Replying to @fchapoton:

Do you want this to be reviewed ? If yes, please turn it into "needs review".

How do I turn it into "needs review" ?

[fchapoton]

comment:13

Click on "Modify ticket", then on the button "needs review". I did it for you.

[videlec]

comment:14

Hello,

This code is very cool! You can have a look at my branch u/vdelecroix/16603 where I provide two commits that I describe below.

• I edited a bit the code, I hope it is cleaner (and actually also a bit faster)

• Please, could you fill the section ALGORITHM of permanental_minor_vector. It would be nice to have here a rough description of the algorithm.

• I edited a lot the documentation. First of all the file matrix_misc.py was not part of the matrix documentation! After my commits it is. If you compile the documentation (with either make doc or sage -docbuild reference html) then you will see the result in the section Matrices and Spaces of Matrices -> Miscellaneous matrix functions. I changed the name _prm_mul to prm_mul in order to make it appear in the documentation.

• Currently the situtation for benchmarks is unfair:

  • the code of Jaap Spies to compute the permanent and the permanent minors can be optimized a lot!
  • your code is in Python while Jaap's one is in Cython

• As you mentioned this algorithm can be used in several contexts. It would be nice to have some methods (of graphs and matrices) that call it. But if you prefer, we can do it in a further ticket.

Vincent

[sagetrac-pernici]

comment:15

Hello,
how can I access your branch u/vdelecroix/16603 ?

[videlec]

comment:16

Replying to @sagetrac-pernici:

Hello,
how can I access your branch u/vdelecroix/16603 ?

How do you do with your branch u/pernici/ticket/16603? All users have write access to public/* and u/username/* and read access everywhere. Just do in the Sage root:

$ git fetch trac u/vdelecroix/16603
$ git checkout -b 16603_vincent_branch FETCH_HEAD

The first command download my two commits. The special temporary branch FETCH_HEAD is a pointer to the last commit. The second command creates a new branch called 16603_vincent_branch and move to it.

You can then merge these commits (if you like them) in your branch with

$ git checkout my_original_branch
$ git merge 16603_vincent_branch

Is that clear enough?

Vincent

[videlec]

Changed branch from u/pernici/ticket/16603 to u/vdelecroix/16603

[videlec]

Reviewer: Vincent Delecroix

[videlec]

comment:29

Hello,

I really think that the documentation is half of a software: it provides specification of functions and help the user to orient himself/herself. Next time you implement a function in Sage pay attention that your new functionality is referenced from other part of the code and that it also make references to relevant functions. There is a lot of possibilities for organization of the documentation (see the section "Docstring" of the developer guide).

I was not happy with the current behavior and documentation of rook_vector and permanental_minor (these methods should work for rectangular matrices whatever their shape). I guess that this is my last commit for that ticket. Just have a look and if you agree we can set the ticket to positive review.

Next step would be optimisation of Ryser algorithm: #17457.

Vincent

---

New commits:

3e7297b

trac #16603: documentation commit

[videlec]

Changed commit from 19350a4 to 3e7297b

[sagetrac-pernici]

Changed branch from u/vdelecroix/16603 to u/pernici/ticket/16603

[sagetrac-pernici]

comment:31

Hello,
I added the matching_polynomial method to the BipartiteGraph class, so one can optionally
use the "rook" algorithm.
Now rook_vector is much faster when the matrix is made mostly of ones.
I fixed a couple of bugs and added documentation.

A simple optimization I did not include here is the one in case of matrices which can be put in block form
permuting rows and columns. I did not include it because it does not seem to be a commonly occurring
case. The same optimization can be used in the computation of determinants of large matrices of this kind.
Do you think that it is worth opening a ticket on it, or is it too obvious and useless?

Sooner or later I will open a ticket for a faster algorithm for the matching polynomial of graphs (non bipartite).

---

New commits:

dd4636a	fixed bug in ``permanental_minor_poly``;
a60cc74	added argument `complement`, eliminated argument `check` in ``rook_vector``;
e4359bb	added ``matching_polynomial`` method to ``BipartiteGraph`` class

[sagetrac-pernici]

Changed commit from 3e7297b to e4359bb

[videlec]

Changed commit from e4359bb to e03f93a

[videlec]

comment:32

Hello,

First of all, there is already a lot of material on this ticket. It would be good to stop here and open tickets for new features (please put me on cc on them).

I push a commit as I do not like the complement keyword that sounds like you want the rook vector of the complement matrix. I replaced it with use_complement. I know that it is different from the specification for BipartiteGraphs but it fits with IndependentSets

sage: from sage.graphs.independent_sets import IndependentSets
sage: I = IndependentSets(graphs.GridGraph((5,5)))
sage: I.cardinality()
55447
sage: I = IndependentSets(graphs.GridGraph((5,5)), complement=True)
sage: I.cardinality()
66

Nevertheless, I kept the keyword complement to do the following as it is very useful

sage: identity_matrix(6).rook_vector(complement=True)
[1, 30, 315, 1420, 2715, 1854, 265]

Vincent

---

New commits:

e03f93a

trac #16603: change keywords for `rook_vector` + doc

[videlec]

Changed branch from u/pernici/ticket/16603 to u/vdelecroix/16603

[sagetrac-pernici]

Changed branch from u/vdelecroix/16603 to u/pernici/ticket/16603

[sagetrac-pernici]

comment:34

Hello,
I made one more small change.
Thank you for reviewing and improving the code and documentation.

---

New commits:

127418f

fixed a bug in ``matching_polynomial``; added test.

[sagetrac-pernici]

Changed commit from e03f93a to 127418f

[videlec]

comment:35

Hello,

Let us stop there with positive review! If you want to go any further open a new ticket (and please put me in cc).

Vincent

[vbraun]

comment:36

Doctest failure in src/sage/misc/sagedoc.py

[videlec]

comment:37

Funny! Done...

---

New commits:

901d36c

fix doctest in misc/sagedoc.py

[videlec]

Changed branch from u/pernici/ticket/16603 to u/vdelecroix/16603

[videlec]

Changed commit from 127418f to 901d36c

[vbraun]

Changed branch from u/vdelecroix/16603 to 901d36c