unweighted matroid intersection using blocking flow approach

[chaoxu]

Implement a unweighted matroid intersection algorithm that uses O(sqrt(p)rn) independence queries by adopting a blocking flow like technique, where r is the rank, p is the size of the maximum common independent set. It is a bit better than the augmenting paths algorithm, which takes O(prn) queries. However, it's expected to perform worse when p is small, since the constant overhead is a bit larger.

William H Cunningham. 1986. Improved bounds for matroid partition and intersection algorithms. SIAM J. Comput. 15, 4 (November 1986), 948-957. DOI=10.1137/0215066 ​http://dx.doi.org/10.1137/0215066

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c9fb292

removed an debugging print out

[chaoxu]

Here is a run time comparison if the maximum common independent set is large.

sage: M = Matroid(MatrixSpace(GF(2), 1000,1000).random_element())
sage: N = Matroid(MatrixSpace(GF(2), 1000,1000).random_element())
sage: %time len(M.intersection(N))
CPU times: user 446 ms, sys: 2.05 ms, total: 448 ms
Wall time: 450 ms
998
sage: %time len(M._intersection_unweighted(N))
CPU times: user 316 ms, sys: 569 us, total: 317 ms
Wall time: 317 ms
998

I have done tests on random matroids and intersection(N) seems to _intersection_unweighted(N). so far so good.

[Stefan]

The runtime seems to depend a lot on the type of matroid.

sage: M1 = Matroid(MatrixSpace(GF(2), 500, 2000).random_element())
sage: M2 = Matroid(MatrixSpace(GF(3), 500, 2000).random_element())
sage: %time X = M1.intersection(M2)
CPU times: user 929 ms, sys: 122 ms, total: 1.05 s
Wall time: 1.05 s
sage: %time X = M1._intersection_unweighted(M2)
CPU times: user 332 ms, sys: 1.68 ms, total: 334 ms
Wall time: 334 ms
sage: M1 = Matroid(MatrixSpace(GF(7), 500, 2000).random_element())
sage: M2 = Matroid(MatrixSpace(GF(3), 500, 2000).random_element())
sage: %time X = M1.intersection(M2)
CPU times: user 37 s, sys: 201 ms, total: 37.2 s
Wall time: 37.2 s
sage: %time X2 = M1._intersection_unweighted(M2)
CPU times: user 5min 1s, sys: 217 ms, total: 5min 1s
Wall time: 5min 2s

Your method is not accessible to end users; mention it in the documentation of the intersection method. After adding that documentation (where you could say something like "a method that might be faster, depending on the matroids involved"), I would say it's good to go in

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e217d9e	faster construction of the graph
​195feb8	update docs

[chaoxu]

This is extremely strange. There are 2 steps in the algorithm. First one is construct the level graph, then do many augmentation in a batch. The bad running time comes from the "construct the level graph" in my code. I have no idea why is my version so much slower. (probably due to ordering of the elements, since it actually use fewer _closure() tests)

I replaced it with the one in _intersection_augmentation() and apparently solved this problem.

This update was done quickly, hence this probably need more testing.

sage: M1 = Matroid(MatrixSpace(GF(7), 500, 2000).random_element())
sage: M2 = Matroid(MatrixSpace(GF(3), 500, 2000).random_element())
sage: %time X = M1.intersection(M2)
CPU times: user 44.6 s, sys: 481 ms, total: 45 s
Wall time: 45.3 s
sage: %time X2 = M1._intersection_unweighted(M2)
CPU times: user 39 s, sys: 52.2 ms, total: 39 s
Wall time: 37.2 s
sage: M1 = Matroid(MatrixSpace(GF(2), 500, 2000).random_element())
sage: M2 = Matroid(MatrixSpace(GF(2), 500, 2000).random_element())
sage: %time X = M1.intersection(M2)
CPU times: user 1.52 s, sys: 332 ms, total: 1.85 s
Wall time: 1.85 s
sage: %time X2 = M1._intersection_unweighted(M2)
CPU times: user 191 ms, sys: 2.93 ms, total: 194 ms
Wall time: 194 ms

[Stefan]

I did a bunch of tests, and the output was always correct. Also, timing tests now show a consistent speedup. It's good to go in as far as I'm concerned!

sage: def test():
    for i in xrange(1000):
            M1 = Matroid(MatrixSpace(GF(7), 50, 2000).random_element())
            M2 = Matroid(MatrixSpace(GF(3), 50, 2000).random_element())
            X = M1.intersection(M2)
....:         
sage: %time test()
CPU times: user 21min 49s, sys: 25.8 s, total: 22min 15s
Wall time: 22min 17s
sage: def test2():
    for i in xrange(1000):
            M1 = Matroid(MatrixSpace(GF(7), 50, 2000).random_element())
            M2 = Matroid(MatrixSpace(GF(3), 50, 2000).random_element())
            X = M1._intersection_unweighted(M2)
....:         
sage: %time test2()
CPU times: user 11min 43s, sys: 936 ms, total: 11min 44s
Wall time: 11min 44s

[vbraun]

Merge conflict, merge in latest beta

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​683e908	Merge branch 'develop' into u/chaoxu/faster-abstract-matroid-intersection
​5514ef8	Merge branch 'develop' into u/chaoxu/faster-abstract-matroid-intersection

[Stefan]

I don't think that last merge went as planned. I can't get it to compile, and after a "git trac try 18946" typing "git diff master" gives a long list of changes unrelated to this ticket.

[chaoxu]

I tried to branch from the current develop, and made the same updates.

The code would look ok with "git diff develop". Or should I actually work with master?

[dimpase]

We typically work with the develop branch. If you work with master, chances are that when time comes to merge the ticket, it won't work. Basing the ready for review ticket on the latest Sage beta is the best way to assume that things will go OK.

[Stefan]

My bad, I was in a hurry and messed up between the two. Code looks fine and Sage builds and runs. Positive review!