Opened 4 years ago

# faster matching polynomial

Reported by: Owned by: pernici major sage-6.6 graph theory vdelecroix, ncohen N/A u/pernici/ticket/17921 (Commits) c87c039e54817c90a98610c3b7a48b575128acec

Added matching_generating_poly, modified matching_polynomial, added an option to permanental_minor_polynomial, which for some graphs is faster than the previous algorithm.

matching_generating_poly computes the matching generating polynomial on (possibly weighted) graphs; this is used in permanental_minor_polynomial.

The algorithm (see [ButPer]) uses polynomials on nilpotent elements, implemented in the class Hobj in matchpoly.pyx. The idea is that the matching generating polynomial can be computed from the product of terms (1 + x w_{i j} \eta_i \eta_j), for all edges (i, j) where w_{i j} is the weight of the edge (i, j) and \eta_i^2 = \eta_j^2=0. The term 1 corresponds to the absence of the dimer (i,j), the other term to its presence. A configuration with two adjacent dimers does not contribute due to nilpotency. The matching generating polynomial is given by the sum of the coefficients of the non-vanishing products of \eta's.

While the result does not depend on the ordering of the edges in the above product, the speed of the algorithm depends on the ordering; in fact doing the above product from left to right, one can set \eta_i=1 as soon as \eta_i does not appear in the yet unused factors on the right, reducing in this way the number of terms. A greedy argument to order edges is contained in active_nodes.py

The Godsil algorithm is faster for small graphs, which take little time with either algorithms; it becomes progressively slower as the number of vertices increases; e.g. on my computer for graphs.KnightGraph([4, n]), the Godsil algorithm for n=5 is 25% faster, for n=6 5x slower, for n=9 4000x slower.

The new algorithm can be much faster than the rook algorithm for matching polynomials of bipartite graphs

sage: time BipartiteGraph(graphs.LadderGraph(30)).matching_polynomial()[0]
Wall time: 65.7 ms
1346269


It is also much faster than the previous algorithm (now called bipartite) for computing the sum of the permanental minors, in the case of randomized band matrices

sage: from sage.matrix.matrix_misc import permanental_minor_polynomial
sage: n, w = 20, 3
sage: m = matrix([[i*j + 1 if abs(i-j) <= w else 0 for i in range(n)] for j in range(n)])
sage: a = list(m); shuffle(a); b = zip(*a); shuffle(b); m1 = matrix(b)
sage: time p1 = permanental_minor_polynomial(m1, algorithm='matching')
Wall time: 174 ms


### comment:1 Changed 4 years ago by pernici

• Branch set to u/pernici/ticket/17921
• Created changed from 03/09/15 19:35:02 to 03/09/15 19:35:02
• Modified changed from 03/09/15 19:35:02 to 03/09/15 19:35:02

### comment:2 Changed 4 years ago by pernici

• Commit set to fe2fa06af8efa606d4bbd6256336c11a93da9a32
• Description modified (diff)

### comment:4 Changed 4 years ago by git

• Commit changed from fe2fa06af8efa606d4bbd6256336c11a93da9a32 to 29612041a35d028109e61b09bba08ea9ec1f8e5e

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

 ​2961204 small change in BipartiteGraph.matching_polynomial

### comment:5 Changed 4 years ago by pernici

• Status changed from new to needs_review

### comment:6 Changed 4 years ago by vdelecroix

• Description modified (diff)
• Status changed from needs_review to needs_info

I clean the description of the ticket to make it readable. Could you try to make it understandable?

### comment:7 Changed 4 years ago by pernici

• Description modified (diff)

### comment:8 Changed 4 years ago by pernici

• Status changed from needs_info to needs_review

### comment:9 Changed 4 years ago by pernici

I added an explanation on the use of nilpotent elements and two more examples.

### comment:10 Changed 4 years ago by pernici

The greedy argument to order edges in active_nodes.py orders edges in such a way that the graph G_i defined by edges[:i] has few nodes which have not the same degree as in G (active nodes). This leads to few \eta_i in the corresponding polynomial, so there are few terms. The greedy algorithm adds edges without increasing the number of active nodes, if possible; otherwise it adds a short path between two active nodes.

This algorithm can be probably improved using some graph algorithm already in Sage, maybe an algorithm to reorder vertices used to visualize graphs.

### comment:11 Changed 4 years ago by rws

Please try to get 100% coverage (sage -coverage) also in private methods. Please adhere to usual documentation guidelines: esp. start paragraphs with big caps, do not use >>> for examples.

### comment:12 Changed 4 years ago by chapoton

• Status changed from needs_review to needs_work

failing doctests, see patchbot report

plus very bad formatting of the doc

### comment:13 Changed 4 years ago by git

• Commit changed from 29612041a35d028109e61b09bba08ea9ec1f8e5e to c87c039e54817c90a98610c3b7a48b575128acec

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

 ​923dcc5 small change in _add_links_no_incr; improved the documentation ​5b10b9e ordered_links has now a single parameter; ​c87c039 renamed _obj_free; used the shorter name "ButPer"

### comment:14 Changed 4 years ago by pernici

• Description modified (diff)

### comment:15 Changed 4 years ago by pernici

• Status changed from needs_work to needs_review

### comment:16 Changed 4 years ago by pernici

• Description modified (diff)

### comment:17 Changed 22 months ago by jdemeyer

• Status changed from needs_review to needs_work

I personally don't care about this ticket, but let me mention that it doesn't apply and that it should be rebased on top of #23126.

Note: See TracTickets for help on using tickets.