Opened 6 years ago
Closed 6 years ago
#18604 closed enhancement (duplicate)
Computing the matching polynomial
Reported by: | azi | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | graph theory | Keywords: | |
Cc: | ncohen, vdelecroix | Merged in: | |
Authors: | Reviewers: | Vincent Delecroix | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Disclaimer: implementing a cache whose keys are (isomorphism type of) graphs and values are some invariant is a bad idea. See comment:1 below.
Original suggestion:
At this point I am not in the right state to include this improvement in Sage but I am leaving it here for the future or if someone else is bored.
Much in the same way as with the chromatic polynomial (as discussed on #14529) one can improve the computation of the matching polynomial with use of caching.
sage: G = graphs.DodecahedralGraph() sage: %timeit G.matching_polynomial() 100 loops, best of 3: 1.97 ms per loop sage: %timeit matchpoly(G) 1 loops, best of 3: 723 µs per loopThe implementation is the usual one though I suppose it makes sense to use this directly in the Cython file.
def matchpoly(G): global cache s = tuple(sorted(G.canonical_label().edges(labels=False))) if s in cache: return cache[s] if not G.is_connected(): return prod([matchpoly(C) for C in G.connected_components_subgraphs()]) R = ZZ['x'] x = R.gen() if G.size() == 0: return x^G.order() u,v = G.edge_iterator(labels=False).next() H = G.copy() H.delete_edge(u,v) p = matchpoly(H) H.delete_vertices([u,v]) ret = p - matchpoly(H) cache[s] = ret return ret
Change History (12)
comment:1 Changed 6 years ago by
comment:2 follow-up: ↓ 3 Changed 6 years ago by
Hey there,
thanks for having a look! I am really surprised about this outcome. The same idea is used for the Tutte polynomial and is a solid improvement. As tested on the Dodecahderal graph it seemed like it makes sense. I guess cache efficiency comes from edge contractions not vertex deletions?
That said I suggest we close this down (can't find the option on my side?)
Jernej
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 5 Changed 6 years ago by
- Description modified (diff)
- Milestone changed from sage-6.8 to sage-duplicate/invalid/wontfix
- Reviewers set to Vincent Delecroix
- Status changed from new to needs_review
Hello,
Replying to azi:
thanks for having a look! I am really surprised about this outcome. The same idea is used for the Tutte polynomial and is a solid improvement. As tested on the Dodecahderal graph it seemed like it makes sense. I guess cache efficiency comes from edge contractions not vertex deletions?
What do you mean by "solid improvement"? Are you sure it is faster to use caching there? Did you do serious benchmarking with and without? I am very curious about that.
That said I suggest we close this down (can't find the option on my side?)
All right.
Vincent
comment:4 Changed 6 years ago by
More precisely this is what I get (with caching):
sage: %time p = G.tutte_polynomial() CPU times: user 184 ms, sys: 8 ms, total: 192 ms Wall time: 186 ms sage: G = graphs.RandomGNP(14, 0.2) sage: %time p = G.tutte_polynomial() CPU times: user 16 ms, sys: 0 ns, total: 16 ms Wall time: 16 ms sage: G = graphs.RandomGNP(14, 0.2) sage: %time p = G.tutte_polynomial() CPU times: user 80 ms, sys: 4 ms, total: 84 ms Wall time: 76.7 ms sage: G = graphs.RandomGNP(14, 0.2) sage: %time p = G.tutte_polynomial() CPU times: user 84 ms, sys: 8 ms, total: 92 ms Wall time: 83.8 ms sage: G = graphs.RandomGNP(14, 0.2) sage: %time p = G.tutte_polynomial() CPU times: user 656 ms, sys: 4 ms, total: 660 ms Wall time: 652 ms sage: %time p = G.tutte_polynomial() CPU times: user 740 ms, sys: 0 ns, total: 740 ms Wall time: 734 ms
without caching (i.e. redefining def _cached(func)
as return func
):
sage: G = graphs.RandomGNP(14, 0.2) sage: %time p = G.tutte_polynomial() CPU times: user 180 ms, sys: 24 ms, total: 204 ms Wall time: 194 ms sage: G = graphs.RandomGNP(14, 0.2) sage: %time p = G.tutte_polynomial() CPU times: user 12 ms, sys: 0 ns, total: 12 ms Wall time: 13.5 ms sage: G = graphs.RandomGNP(14, 0.2) sage: %time p = G.tutte_polynomial() CPU times: user 16 ms, sys: 4 ms, total: 20 ms Wall time: 19.5 ms sage: G = graphs.RandomGNP(14, 0.2) sage: %time p = G.tutte_polynomial() CPU times: user 28 ms, sys: 0 ns, total: 28 ms Wall time: 27.1 ms sage: G = graphs.RandomGNP(14, 0.2) sage: %time p = G.tutte_polynomial() CPU times: user 80 ms, sys: 4 ms, total: 84 ms Wall time: 75.8 ms sage: G = graphs.RandomGNP(14, 0.2) sage: %time p = G.tutte_polynomial() CPU times: user 8 ms, sys: 0 ns, total: 8 ms Wall time: 7.01 ms sage: G = graphs.RandomGNP(14, 0.2) sage: %time p = G.tutte_polynomial() CPU times: user 44 ms, sys: 0 ns, total: 44 ms Wall time: 39.1 ms
So I wonder where is your "solid improvement"!?
Vincent
comment:5 in reply to: ↑ 3 Changed 6 years ago by
Replying to vdelecroix:
Hello,
Replying to azi:
thanks for having a look! I am really surprised about this outcome. The same idea is used for the Tutte polynomial and is a solid improvement. As tested on the Dodecahderal graph it seemed like it makes sense. I guess cache efficiency comes from edge contractions not vertex deletions?
What do you mean by "solid improvement"? Are you sure it is faster to use caching there? Did you do serious benchmarking with and without? I am very curious about that.
Yep the improvement in such cases is well know. There is actually even a paper that describes this idea. See the paper cited here http://homepages.ecs.vuw.ac.nz/~djp/tutte/
That said I suggest we close this down (can't find the option on my side?)
All right.
Vincent
comment:6 Changed 6 years ago by
I see... Thanks for the link. Apparently, Sage is not smart enough to make a difference here ;-)
Vincent
comment:7 Changed 6 years ago by
Yep. Perhaps one of the bottlenecks is that canonical forms in Sage is (currently) written in Python and the algorithm itself is not the most efficient (as far as I've compared with say nauty)
comment:8 Changed 6 years ago by
So perhaps this ticket would still makes sense?
comment:9 Changed 6 years ago by
In some sense it does but one would really have to be careful in designing this properly.
You argued that on random graphs on 14 vertices is less efficient and if we take that as our base benchmark then it may not be worth it.
In general I think it can be made in a worthwhile improvement especially for larger graphs and provided that we use bliss or nauty.
comment:10 Changed 6 years ago by
Does this ticket still needs a review? #17921 also claims to make this routine faster.
comment:11 Changed 6 years ago by
- Status changed from needs_review to positive_review
The algorithm in #17921 has a speed factor of >1000x for the bigger examples given here, so this is a complete different game. There is the original Sage algorithm if one needs a check.
comment:12 Changed 6 years ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
Hi,
Your proposition is far from being a computational improvement. Caching the values of all possible graphs results in using a lot of memory. Moreover, for most graphs your proposition would be slower (because you call for canonical labels).
For very symmetric graph of a reasonable size your function is already slower
And it is infinitely slower on random graphs
Of course the next call would be faster but I do not know anybody who will call twice an expensive function.
I propose to just close this ticket as a won't fix and emphasize in the description that caching is of no help here! If you care about the computation of matching polynomial you can have a look at #17921.
Vincent