Improve efficiency of minors() for BinaryMatroid, TernaryMatroid, QuaternaryMatroid

[sagetrac-Rudi]

The representing matrices of BinaryMatroid, TernaryMatroid, QuaternaryMatroid, are bitpacket. Taking minors, involves constructing a submatrix of such a representing matrix. Since the rows are bitpacked, the relocation of columns in particular is relatively inefficient.

By allowing a submatrix in which the columns are allowed to be permuted, it is possible to reduce the number of column relocations to at most the number of deleted columns, and this will be far more efficient than the current implementation, especially if few columns are deleted.

CC: @chaoxu @sagetrac-Stefan @sagetrac-yomcat

Component: matroid theory

Author: Rudi Pendavingh

Branch/Commit: a5fd2f5

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/18660

[sagetrac-Rudi]

comment:1

Still need to try this out. Hope to do this this week.

Since a cocircuit of a binary matroid M is typically going to have size about r^*(M) /2 elements, I expect a speedup by a factor of up to r^*(M)/2/|E(M)| for the minor-taking in Chao's code in ticket #18539.

[sagetrac-Rudi]

Branch: u/Rudi/improve_efficiency_of_minors___for_binarymatroid__ternarymatroid__quaternarymatroid

[sagetrac-Rudi]

Commit: 7deb135

[sagetrac-Rudi]

comment:3

First worked on BinaryMatroid and BinaryMatrix. The new code seems to be correct:

sage: N = Matroid(MatrixSpace(GF(2), 5,12).random_element())
sage: for X in subsets(N.groundset()):
    if not BasisMatroid(N\X).equals(BasisMatroid(N)\X):
        print X

It's more efficient too. Without the patch:

sage: M = Matroid(MatrixSpace(GF(2), 500,1000).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 3.69 s per loop

With the patch:

sage: M = Matroid(MatrixSpace(GF(2), 500,1000).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 692 ms per loop

So, about 5 times faster on this example. This is not all due to the trick announced in the ticket. Replacing a list by a c-style array here and there did some good too. And just replacing the line

C = [c for c in range(len(self._E)) if self._E[c] not in deletions | contractions]

in _minor by something that does not compute the union deletions | contractions for each c made the code 2 times faster right there.

---

New commits:

7deb135

Added new method for taking submatrix of a BinaryMatrix, used in BinaryMatroid._minor()

[sagetrac-git]

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

3ea8ac5

Improved Ternary and Quaternary along the same lines

[sagetrac-git]

Changed commit from 7deb135 to 3ea8ac5

[sagetrac-Rudi]

comment:5

Correctness:

sage: N = Matroid(MatrixSpace(GF(2), 5,10).random_element())
sage: for X in subsets(N.groundset()):
    for Y in subsets(N.groundset()-set(X)):
        if not BasisMatroid(N.minor(X,Y)).equals(BasisMatroid(N).minor(X,Y)):
            print X,Y
....:             
sage: N = Matroid(MatrixSpace(GF(3), 5,10).random_element())
sage: for X in subsets(N.groundset()):
    for Y in subsets(N.groundset()-set(X)):
        if not BasisMatroid(N.minor(X,Y)).equals(BasisMatroid(N).minor(X,Y)):
            print X,Y
....:             
sage: N = Matroid(MatrixSpace(GF(4,x), 5,10).random_element())
sage: for X in subsets(N.groundset()):
    for Y in subsets(N.groundset()-set(X)):
        if not BasisMatroid(N.minor(X,Y)).equals(BasisMatroid(N).minor(X,Y)):
            print X,Y

Efficiency before patch:

sage: M = Matroid(MatrixSpace(GF(2), 200,400).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 261 ms per loop
sage: M = Matroid(MatrixSpace(GF(3), 200,400).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 7.13 s per loop
sage: M = Matroid(MatrixSpace(GF(4,x), 200,400).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 3.95 s per loop

Efficiency after patch:

sage: M = Matroid(MatrixSpace(GF(2), 200,400).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 73.7 ms per loop
sage: M = Matroid(MatrixSpace(GF(3), 200,400).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 86.7 ms per loop
sage: M = Matroid(MatrixSpace(GF(4,x), 200,400).random_element())
sage: B = M.basis()
sage: timeit("for e in B: M.delete(M._fundamental_cocircuit(B,e))")
5 loops, best of 3: 86.4 ms per loop

For TernaryMatrix and QuaternaryMatrix, there was no optimized submatrix-code to begin with, hence the 40 - 80 times speedup.
I scaled down the size of the matrix a bit, the ternary benchmark simply wouldn't finish for 500x1000.

I will remove some lingering cython profile directives, and then I'm done.

[sagetrac-git]

Changed commit from 3ea8ac5 to 20dc896

[sagetrac-git]

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

20dc896

Cleaned up profiler directives

[sagetrac-Rudi]

Author: Rudi Pendavingh

[sagetrac-git]

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

a5fd2f5

removed trailing whitespace

[sagetrac-git]

Changed commit from 20dc896 to a5fd2f5

[sagetrac-Rudi]

comment:9

Before:

sage: M = Matroid(MatrixSpace(GF(3), 500,1000).random_element())
sage: timeit("M.delete([0])")
5 loops, best of 3: 333 ms per loop

After:

sage: M = Matroid(MatrixSpace(GF(3), 500,1000).random_element())
sage: timeit("M.delete([0])")
625 loops, best of 3: 655 µs per loop

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:10

LGTM. I'm slightly unhappy with the fact that it looks like a lot of logic is duplicated across the multiple matrix_from_rows_and_columns_reordered, but I don't see a way to really combine the common logic. So positive review.

[sagetrac-Rudi]

comment:11

Replying to @tscrim:

LGTM. I'm slightly unhappy with the fact that it looks like a lot of logic is duplicated across the multiple matrix_from_rows_and_columns_reordered, but I don't see a way to really combine the common logic. So positive review.

Thanks for the review.

[vbraun]

Changed branch from u/Rudi/improve_efficiency_of_minors___for_binarymatroid__ternarymatroid__quaternarymatroid to a5fd2f5