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 )
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
- 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
- Cc vdelecroix added
- Commit set to fe2fa06af8efa606d4bbd6256336c11a93da9a32
- Description modified (diff)
comment:3 Changed 4 years ago by
- Cc ncohen added
comment:4 Changed 4 years ago by
- Commit changed from fe2fa06af8efa606d4bbd6256336c11a93da9a32 to 29612041a35d028109e61b09bba08ea9ec1f8e5e
comment:5 Changed 4 years ago by
- Status changed from new to needs_review
comment:6 Changed 4 years ago by
- 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
- Description modified (diff)
comment:8 Changed 4 years ago by
- Status changed from needs_info to needs_review
comment:9 Changed 4 years ago by
I added an explanation on the use of nilpotent elements and two more examples.
comment:10 Changed 4 years ago by
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
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
- 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
- Commit changed from 29612041a35d028109e61b09bba08ea9ec1f8e5e to c87c039e54817c90a98610c3b7a48b575128acec
comment:14 Changed 4 years ago by
- Description modified (diff)
comment:15 Changed 4 years ago by
- Status changed from needs_work to needs_review
comment:16 Changed 4 years ago by
- Description modified (diff)
comment:17 Changed 2 years ago by
- 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.
Branch pushed to git repo; I updated commit sha1. New commits:
small change in ``BipartiteGraph.matching_polynomial``