Hi Volker, and everyone else on sage-devel, I did some speed tests with an old version of the code that still used Sage matrices (commit 6d9e689 on bitbucket, with a few tweaks to make it run on Sage 5.10.beta4). Each of these tests performs a matroid computation through extensive pivoting.
I ran three versions of the test: * Sage matrices * Same algorithm, using a LeanMatrix instance * Optimized algorithm for this class of matroids for four different classes of matroids: * Binary * Ternary * Quaternary * Regular Without patch 14627 (on Sage 5.9.beta3): Comparing the speed of various classes. ========================================================== Binary matroids: Sage matrix: 5 loops, best of 5: 101 ms per loop lean_matrix.BinaryMatrix: 5 loops, best of 5: 21.2 ms per loop BinaryMatroid and BinaryMatrix: 5 loops, best of 5: 3.08 ms per loop ========================================================== Ternary matroids: Sage matrix: 5 loops, best of 5: 5.7 s per loop lean_matrix.TernaryMatrix: 5 loops, best of 5: 1.29 s per loop TernaryMatroid: 5 loops, best of 5: 7.98 ms per loop ========================================================== Quaternary matroids: Sage matrix: 5 loops, best of 5: 186 ms per loop lean_matrix.QuaternaryMatrix: 5 loops, best of 5: 205 ms per loop QuaternaryMatroid and QuaternaryMatrix: 5 loops, best of 5: 13.4 ms per loop ========================================================== Regular matroids: Sage matrix: 5 loops, best of 5: 753 ms per loop lean_matrix.IntegerMatrix: 5 loops, best of 5: 49.3 ms per loop RegularMatroid and IntegerMatrix: 5 loops, best of 5: 19.8 ms per loop With patch 14627 (on Sage 5.10.beta4): Comparing the speed of various classes. ========================================================== Binary matroids: Sage matrix: 5 loops, best of 5: 91.2 ms per loop lean_matrix.BinaryMatrix: 5 loops, best of 5: 21.4 ms per loop BinaryMatroid and BinaryMatrix: 5 loops, best of 5: 3.24 ms per loop ========================================================== Ternary matroids: Sage matrix: 5 loops, best of 5: 240 ms per loop lean_matrix.TernaryMatrix: 5 loops, best of 5: 1.2 s per loop TernaryMatroid: 5 loops, best of 5: 8.17 ms per loop ========================================================== Quaternary matroids: Sage matrix: 5 loops, best of 5: 434 ms per loop lean_matrix.QuaternaryMatrix: 5 loops, best of 5: 162 ms per loop QuaternaryMatroid and QuaternaryMatrix: 5 loops, best of 5: 11.3 ms per loop ========================================================== Regular matroids: Sage matrix: 5 loops, best of 5: 687 ms per loop lean_matrix.IntegerMatrix: 5 loops, best of 5: 45.7 ms per loop RegularMatroid and IntegerMatrix: 5 loops, best of 5: 18.6 ms per loop Conclusions: The only speedup obtained from 14627 is for prime fields (and it is HUGE: a factor 20). But our custom class still outperforms Sage's matrices by at least a factor 3 much of the time. With the more specialized routines that exploit the bit packed representation of the matrix, the speedup is even more significant. It will require significant effort to bring Sage's matrices up to the same speed. For ternary matroids, it won't happen until Martin Albrecht has generalized M4Ri(e) to fields of other characteristic. So I propose to keep the LeanMatrix code for now, opening a ticket titled something like "Bring Sage matrices into the matroid code without performance loss" for a later date. --Stefan. P.S. It looks like GF(4)-matrices had a speed regression between 5.9 and 5.10?! On 25 mei 2013, at 12:58, Volker Braun wrote: > If that is actually the bottleneck then the relevant matrices just need to > override add_multiple_of_row_c with a specialized version instead of using > the generic one from matrix0. > > It seems that renaming Sage's add_multiple_of_row() into row_add() etc. in > your code is just making it unnecessarily difficult to switch to Sage > matrices. > > > > On Saturday, May 25, 2013 4:40:40 PM UTC+1, Stefan wrote: > cdef bint __exchange(self, long x, long y): > """ > Put element indexed by ``x`` into basis, taking out element ``y``. > Assumptions are that this is a valid basis exchange. > > .. NOTE:: > > Safe for noncommutative rings. > """ > cdef long px, py, r > px = self._prow[x] > py = self._prow[y] > piv = self._A.get_unsafe(px, py) > pivi = piv ** (-1) > self._A.row_scale(px, pivi) > self._A.set_unsafe(px, py, pivi + self._one) # pivoting without > column scaling. Add extra so column does not need adjusting > for r in xrange(self._A.nrows()): # if A and A' are the > matrices before and after pivoting, then > a = self._A.get_unsafe(r, py) # ker[I A] equals ker[I A'] > except for the labelling of the columns > if a and r != px: > self._A.row_add(r, px, -a) > self._A.set_unsafe(px, py, pivi) > self._prow[y] = px > self._prow[x] = py > BasisExchangeMatroid.__exchange(self, x, y) > > --Stefan. > > -- > > --- > You received this message because you are subscribed to the Google Groups > "sage-matroid" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-matroid+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
