#19027: matroid partitioning, matroid union
-------------------------------------+-------------------------------------
Reporter: chaoxu | Owner:
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-6.9
Component: matroid theory | Resolution:
Keywords: | Merged in:
Authors: Chao Xu | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/chaoxu/unionmatroid | a83ef240ad902c14e679db54754d241c89dbaaaf
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Chao Xu', 'oldvalue': ''}):
* author: => Chao Xu
Comment:
Replying to [comment:4 ncohen]:
> Wow. Matroid union. I've been hoping that it would come true for a
looooong time. There is a graph function that "screams" for that:
`Graph.edge_disjoint_spanning_trees` `:-P`
There are still 2 barriers to using matroid union for
`Graph.edge_disjoint_spanning_trees`.
1. The algorithm is slow and likely can't surpass a highly optimized
integer program implementation for reasonable input sizes. (#18946 will
speed things up a lot)
2. The current implementation of matroid union is a reduction to matroid
intersection. We can find min base covering but not max base packing. I'm
not sure how to get the packing version other than implement a direct
matroid union algorithm.
Matroid union and matroid partition have similar running time. (both
reduces to matroid intersection of a matroid sum and a partition matroid)
A rough estimate for matroid partition running time is O(n^3^Q) where Q is
the time for independence oracle query, n is the size of the groundset.
For a graphic matroid of only 60 elements, it took 30 seconds! (in the
worst case Q can be as bad as O(r^3^) because we use linear matroid to
implement graphic matroid. Here r is the rank of the matroid) The rank
computation is almost 100% of the running time.
The good news is that the algorithm in #18946 speeds things up greatly.
Just replace all occurrence of `intersection` with
`_intersection_unweighted`. The process that took 30 seconds originally
took less than 2 seconds. A closer inspection shows it uses much fewer
rank computations, not because of faster rank computations.
But a faster rank computations would be even more helpful. We are suppose
to expect running time of O(n^3^) in linear matroids if pivoting are done
in the right order [Cunningham 1986, the same paper in #18946].
Here is the actual run time breakdown of that 30 second computation. See
`basis_exchange_matroid.pyx:670(_rank)`.
{{{
sage: M=Matroid(graphs.RandomRegular(3,40)))
sage: %prun M.partition()
114970426 function calls in 31.515 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1753573 10.459 0.000 11.930 0.000
linear_matroid.pyx:5506(__exchange)
309403 5.859 0.000 28.289 0.000
basis_exchange_matroid.pyx:271(__move)
18323845 5.128 0.000 7.242 0.000 bitset.pxi:466(bitset_next)
7828013 1.310 0.000 1.758 0.000 bitset.pxi:356(bitset_add)
18245089 1.082 0.000 1.082 0.000
bitset.pxi:408(_bitset_first_in_limb)
18245090 1.031 0.000 1.031 0.000
bitset.pxi:55(limb_lower_bits_down)
309403 1.021 0.000 2.368 0.000
basis_exchange_matroid.pyx:236(__pack)
13592459 1.016 0.000 1.016 0.000
linear_matroid.pyx:5500(__is_exchange_pair)
6907871 1.005 0.000 1.326 0.000 bitset.pxi:417(bitset_first)
5260719 0.937 0.000 1.251 0.000
bitset.pxi:341(bitset_discard)
1753573 0.597 0.000 1.471 0.000
basis_exchange_matroid.pyx:264(__exchange)
7828013 0.448 0.000 0.448 0.000
bitset.pxi:43(limb_one_set_bit)
5429232 0.321 0.000 0.321 0.000
bitset.pxi:401(_bitset_first_in_limb_nonzero)
5260719 0.315 0.000 0.315 0.000
bitset.pxi:49(limb_one_zero_bit)
1830 0.298 0.000 0.311 0.000 matroid.pyx:537(_circuit)
309402 0.209 0.000 28.571 0.000
basis_exchange_matroid.pyx:318(__max_independent)
309402 0.176 0.000 31.140 0.000
basis_exchange_matroid.pyx:670(_rank)
1753573 0.104 0.000 0.104 0.000
bitset.pxi:199(bitset_isempty)
61 0.063 0.001 32.689 0.536
matroid.pyx:6015(_intersection_augmentation)
618845 0.044 0.000 0.044 0.000
bitset.pxi:584(bitset_difference)
309402 0.028 0.000 0.028 0.000
bitset.pxi:546(bitset_intersection)
309402 0.025 0.000 0.025 0.000 bitset.pxi:504(bitset_len)
309442 0.024 0.000 0.024 0.000 bitset.pxi:121(bitset_clear)
1830 0.012 0.000 0.012 0.000
matroid.pyx:808(_is_independent)
1 0.001 0.001 32.689 32.689
matroid.pyx:5975(_intersection)
39 0.000 0.000 0.001 0.000
basis_exchange_matroid.pyx:291(__fundamental_cocircuit)
61 0.000 0.000 0.033 0.001 matroid.pyx:599(_closure)
1 0.000 0.000 32.689 32.689
matroid.pyx:5917(intersection)
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/19027#comment:5>
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.
