Opened 8 years ago
Closed 7 years ago
#18946 closed enhancement (fixed)
unweighted matroid intersection using blocking flow approach
Reported by: | chaoxu | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.9 |
Component: | matroid theory | Keywords: | |
Cc: | Stefan, yomcat, Rudi | Merged in: | |
Authors: | Chao Xu | Reviewers: | Stefan van Zwam |
Report Upstream: | N/A | Work issues: | |
Branch: | 37f2c3b (Commits, GitHub, GitLab) | Commit: | 37f2c3bf0ac81d4e422bdcdb5f2ede05c512cab8 |
Dependencies: | Stopgaps: |
Description
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
Change History (19)
comment:1 Changed 8 years ago by
Branch: | → u/chaoxu/faster-abstract-matroid-intersection |
---|
comment:2 Changed 8 years ago by
Commit: | → c9fb292e9d2155ddc647e83970204a256ae53b3f |
---|
comment:3 Changed 8 years ago by
Status: | new → needs_review |
---|
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.
comment:4 Changed 7 years ago by
Milestone: | sage-6.8 → sage-6.9 |
---|
comment:5 Changed 7 years ago by
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
comment:6 Changed 7 years ago by
Status: | needs_review → needs_work |
---|
comment:7 Changed 7 years ago by
Commit: | c9fb292e9d2155ddc647e83970204a256ae53b3f → 195feb847638db2c2b1763a1283c9ef31a81fa25 |
---|
comment:8 Changed 7 years ago by
Status: | needs_work → needs_review |
---|
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
comment:9 Changed 7 years ago by
Authors: | → Chao Xu |
---|---|
Reviewers: | → Stefan van Zwam |
Status: | needs_review → positive_review |
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
comment:10 Changed 7 years ago by
Status: | positive_review → needs_work |
---|
Merge conflict, merge in latest beta
comment:11 Changed 7 years ago by
Commit: | 195feb847638db2c2b1763a1283c9ef31a81fa25 → 5514ef89326e9dc7cba4580f817a1e4cd95087d3 |
---|
comment:12 Changed 7 years ago by
Status: | needs_work → needs_review |
---|
comment:13 Changed 7 years ago by
Status: | needs_review → needs_work |
---|
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.
comment:14 Changed 7 years ago by
Branch: | u/chaoxu/faster-abstract-matroid-intersection |
---|---|
Commit: | 5514ef89326e9dc7cba4580f817a1e4cd95087d3 |
comment:15 Changed 7 years ago by
Branch: | → u/chaoxu/faster-abstract-matroid-intersection-new |
---|
comment:16 Changed 7 years ago by
Commit: | → 37f2c3bf0ac81d4e422bdcdb5f2ede05c512cab8 |
---|---|
Status: | needs_work → needs_info |
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?
comment:17 Changed 7 years ago by
Status: | needs_info → needs_review |
---|
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.
comment:18 Changed 7 years ago by
Status: | needs_review → positive_review |
---|
My bad, I was in a hurry and messed up between the two. Code looks fine and Sage builds and runs. Positive review!
comment:19 Changed 7 years ago by
Branch: | u/chaoxu/faster-abstract-matroid-intersection-new → 37f2c3bf0ac81d4e422bdcdb5f2ede05c512cab8 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Branch pushed to git repo; I updated commit sha1. New commits:
removed an debugging print out