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 |

**Note:**See TracTickets for help on using tickets.

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

`removed an debugging print out`