On Saturday, May 25, 2013 11:22:38 AM UTC-4, Volker Braun wrote:
> On Saturday, May 25, 2013 3:51:06 PM UTC+1, Stefan wrote:
>
>> There's likely to be some performance loss even when all obvious
>> bottlenecks are accounted for, because for our special classes
>> BinaryMatrix, TernaryMatrix, QuaternaryMatrix we use inline get() and set()
>> methods that bypass the Sage finite field elements.
>>
>
> Only if get/setting matrix elements is actually the bottleneck. But once
> you are actually doing something with the matrices then e.g.
> Strassen-Winograd will run circles around the naive O(N^3) multiplication
> that you have in there.
>
Multiplication occurs only a handful of times (when computing invariants).
The real bottleneck is this method (focus on self._A which is the matrix):
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-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.
