#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|
84a81fdefe60c488faf9e4610c170c985e0c5f2f
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by chaoxu):
Replying to [comment:13 Rudi]:
> I have attached the set of matroids on at most 9 elements, perhaps that
will save you some time translating their data.
Thanks, that's really helpful. I found a bug and now it have been fixed.
Now it works for all test cases. I'm pretty convinced of the correctness.
> What part of your code is currently using most of the time on these test
cases?
For the named cases, _corank and minor operation taking the most of the
time.
For the small 3 connected binary matroids, most time was spent on
is_circuit, is_cosimple, is_simple.
For matroids with large rank (I generated a random rank 500 binary
matroid), components take the most time.
Here is an time breakdown for a rank 500 binary matroid.
{{{
136529 function calls in 18.426 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
501 6.947 0.014 11.109 0.022 matroid.pyx:4477(components)
125515 4.162 0.000 4.162 0.000 matroid.pyx:1351(circuit)
1 3.968 3.968 3.968 3.968
matroid.pyx:4441(is_cosimple)
500 3.216 0.006 3.246 0.006 matroid.pyx:3438(minor)
1 0.027 0.027 14.356 14.356
matroid.pyx:4807(_is_3connected_beta)
1000 0.026 0.000 0.044 0.000
matroid.pyx:1772(fundamental_cocircuit)
1 0.026 0.026 0.026 0.026 matroid.pyx:4408(is_simple)
1000 0.014 0.000 0.014 0.000 matroid.pyx:820(_is_basis)
500 0.013 0.000 0.013 0.000 {method '_max_coindependent'
of 'sage.matroids.basis_exchange_matroid.BasisExchangeMatroid' objects}
500 0.005 0.000 0.030 0.000
utilities.py:184(sanitize_contractions_deletions)
1 0.005 0.005 0.005 0.005 matroid.pyx:2040(coloops)
500 0.005 0.000 0.005 0.000 {method '_max_independent'
of 'sage.matroids.basis_exchange_matroid.BasisExchangeMatroid' objects}
1000 0.003 0.000 0.017 0.000 matroid.pyx:1887(is_basis)
1000 0.003 0.000 0.003 0.000 {method 'issuperset' of
'frozenset' objects}
1000 0.002 0.000 0.002 0.000 {method 'difference' of
'frozenset' objects}
1000 0.002 0.000 0.002 0.000 {method 'union' of
'frozenset' objects}
500 0.001 0.000 3.248 0.006 matroid.pyx:3631(delete)
500 0.000 0.000 11.060 0.022
matroid.pyx:4518(is_connected)
500 0.000 0.000 0.000 0.000 {method 'isdisjoint' of
'frozenset' objects}
1000 0.000 0.000 0.000 0.000 {method 'groundset' of
'sage.matroids.basis_exchange_matroid.BasisExchangeMatroid' objects}
1 0.000 0.000 0.000 0.000 matroid.pyx:1811(loops)
1 0.000 0.000 18.431 18.431 <string>:1(<module>)
1 0.000 0.000 18.431 18.431 {method 'is_3connected_beta'
of 'sage.matroids.matroid.Matroid' objects}
1 0.000 0.000 18.431 18.431
matroid.pyx:4740(is_3connected_beta)
3 0.000 0.000 0.000 0.000 matroid.pyx:1216(size)
1 0.000 0.000 0.000 0.000 matroid.pyx:1236(rank)
1 0.000 0.000 0.000 0.000 {method 'disable' of
'_lsprof.Profiler' objects}
}}}
I will get it to return a separator and write some docs for the next
update.
--
Ticket URL: <http://trac.sagemath.org/ticket/18539#comment:16>
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.
