#18539: faster matroid 3 connectivity
-------------------------------------+-------------------------------------
Reporter: chaoxu | Owner: chaoxu
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.8
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/chaoxu/faster_matroid_3_connectivity|
0033334e6a0795d4e6033ac4721f3a8f432e7b55
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by chaoxu):
Thanks Rudi, I have incorporated your suggestions. It's much faster now.
One can use the following code to test the running time of the current
implementation and the original one.
{{{
def bench(beta=False):
for M in matroids.named_matroids.__dict__.values():
if callable(M):
if beta:
M().is_3connected_beta()
else:
M().is_3connected()
}}}
{{{
sage: %time bench(False)
CPU times: user 298 ms, sys: 10.5 ms, total: 309 ms
Wall time: 301 ms
sage: %time bench(True)
CPU times: user 36.9 ms, sys: 1.83 ms, total: 38.8 ms
Wall time: 37.5 ms
}}}
I also benchmarked on 3-connected binary matroids
[https://groups.google.com/d/msg/sage-matroid/invXwv8SYsE/8tXA2hYUluEJ
listed here]. The old algorithm takes 925 ms, the new one takes 51 ms.
For correctness, I will try to see if the original and the new
implementation agrees for all matroids with at most 9 elements. (data from
[http://www-imai.is.s.u-tokyo.ac.jp/~ymatsu/matroid/index.html Database of
Matroids]).
--
Ticket URL: <http://trac.sagemath.org/ticket/18539#comment:12>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
