Opened 6 years ago
Closed 5 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) | 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 6 years ago by
- Branch set to u/chaoxu/faster-abstract-matroid-intersection
comment:2 Changed 6 years ago by
- Commit set to c9fb292e9d2155ddc647e83970204a256ae53b3f
comment:3 Changed 6 years ago by
- Status changed from new to 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 5 years ago by
- Milestone changed from sage-6.8 to sage-6.9
comment:5 Changed 5 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 5 years ago by
- Status changed from needs_review to needs_work
comment:7 Changed 5 years ago by
- Commit changed from c9fb292e9d2155ddc647e83970204a256ae53b3f to 195feb847638db2c2b1763a1283c9ef31a81fa25
comment:8 Changed 5 years ago by
- Status changed from needs_work to 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 5 years ago by
- Reviewers set to Stefan van Zwam
- Status changed from needs_review to 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 5 years ago by
- Status changed from positive_review to needs_work
Merge conflict, merge in latest beta
comment:11 Changed 5 years ago by
- Commit changed from 195feb847638db2c2b1763a1283c9ef31a81fa25 to 5514ef89326e9dc7cba4580f817a1e4cd95087d3
comment:12 Changed 5 years ago by
- Status changed from needs_work to needs_review
comment:13 Changed 5 years ago by
- Status changed from needs_review to 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 5 years ago by
- Branch u/chaoxu/faster-abstract-matroid-intersection deleted
- Commit 5514ef89326e9dc7cba4580f817a1e4cd95087d3 deleted
comment:15 Changed 5 years ago by
- Branch set to u/chaoxu/faster-abstract-matroid-intersection-new
comment:16 Changed 5 years ago by
- Commit set to 37f2c3bf0ac81d4e422bdcdb5f2ede05c512cab8
- Status changed from needs_work to 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 5 years ago by
- Status changed from needs_info to 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 5 years ago by
- Status changed from needs_review to 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 5 years ago by
- Branch changed from u/chaoxu/faster-abstract-matroid-intersection-new to 37f2c3bf0ac81d4e422bdcdb5f2ede05c512cab8
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
removed an debugging print out