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 chaoxu

  • Branch set to u/chaoxu/faster-abstract-matroid-intersection

comment:2 Changed 6 years ago by git

  • Commit set to c9fb292e9d2155ddc647e83970204a256ae53b3f

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

c9fb292removed an debugging print out

comment:3 Changed 6 years ago by chaoxu

  • 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 dimpase

  • Milestone changed from sage-6.8 to sage-6.9

comment:5 Changed 5 years ago by 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

comment:6 Changed 5 years ago by Stefan

  • Status changed from needs_review to needs_work

comment:7 Changed 5 years ago by git

  • Commit changed from c9fb292e9d2155ddc647e83970204a256ae53b3f to 195feb847638db2c2b1763a1283c9ef31a81fa25

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

e217d9efaster construction of the graph
195feb8update docs

comment:8 Changed 5 years ago by chaoxu

  • 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 Stefan

  • Authors set to Chao Xu
  • 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 vbraun

  • Status changed from positive_review to needs_work

Merge conflict, merge in latest beta

comment:11 Changed 5 years ago by git

  • Commit changed from 195feb847638db2c2b1763a1283c9ef31a81fa25 to 5514ef89326e9dc7cba4580f817a1e4cd95087d3

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

683e908Merge branch 'develop' into u/chaoxu/faster-abstract-matroid-intersection
5514ef8Merge branch 'develop' into u/chaoxu/faster-abstract-matroid-intersection

comment:12 Changed 5 years ago by chaoxu

  • Status changed from needs_work to needs_review

comment:13 Changed 5 years ago by Stefan

  • 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 chaoxu

  • Branch u/chaoxu/faster-abstract-matroid-intersection deleted
  • Commit 5514ef89326e9dc7cba4580f817a1e4cd95087d3 deleted

comment:15 Changed 5 years ago by chaoxu

  • Branch set to u/chaoxu/faster-abstract-matroid-intersection-new

comment:16 Changed 5 years ago by chaoxu

  • 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 dimpase

  • 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.

Last edited 5 years ago by dimpase (previous) (diff)

comment:18 Changed 5 years ago by Stefan

  • 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 vbraun

  • Branch changed from u/chaoxu/faster-abstract-matroid-intersection-new to 37f2c3bf0ac81d4e422bdcdb5f2ede05c512cab8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.