Opened 4 years ago

Last modified 2 years ago

#17921 needs_work enhancement

faster matching polynomial

Reported by: pernici Owned by:
Priority: major Milestone: sage-6.6
Component: graph theory Keywords:
Cc: vdelecroix, ncohen Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/pernici/ticket/17921 (Commits) Commit: c87c039e54817c90a98610c3b7a48b575128acec
Dependencies: Stopgaps:

Description (last modified by pernici)

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

Change History (17)

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

  • Cc vdelecroix added
  • Commit set to fe2fa06af8efa606d4bbd6256336c11a93da9a32
  • Description modified (diff)

comment:3 Changed 4 years ago by ncohen

  • Cc ncohen added

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:

2961204small 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:

923dcc5small change in ``_add_links_no_incr``; improved the documentation
5b10b9e``ordered_links`` has now a single parameter;
c87c039renamed `_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 2 years 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.