Sage: Ticket #9888: matrix multiplication over integer mod ring is slow
https://trac.sagemath.org/ticket/9888
<p>
Sage 4.5.3, 2.6GHz Opteron, Linux
</p>
<p>
This is ok:
</p>
<pre class="wiki">sage: M1 = Matrix([[randrange(3^20) for i in range(100)] for j in range(100)])
sage: M2 = Matrix([[randrange(3^20) for i in range(100)] for j in range(100)])
sage: timeit("M3 = M1 * M2")
5 loops, best of 3: 45.6 ms per loop
</pre><p>
(That's about 4 times slower than Magma, but I can put up with that, that's a ticket for another day.)
</p>
<p>
Here is the problem:
</p>
<pre class="wiki">sage: R = Integers(3^20)
sage: M1 = Matrix([[R.random_element() for i in range(100)] for j in range(100)])
sage: M2 = Matrix([[R.random_element() for i in range(100)] for j in range(100)])
sage: timeit("M3 = M1 * M2")
5 loops, best of 3: 877 ms per loop
</pre><p>
In other words, I can multiply the matrices over R roughly 20x faster by multiplying over Z and then reducing! That's ridiculous!
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/9888
Trac 1.1.6robertwbThu, 09 Sep 2010 16:29:27 GMT
https://trac.sagemath.org/ticket/9888#comment:1
https://trac.sagemath.org/ticket/9888#comment:1
<p>
I don't think anything has gone into non-word-sized modulus, so this is probably using totally generic per-element wrapping code :(. Should be an easy fix to get better than this, doing something real would be a bit more work.
</p>
TicketkedlayaSun, 10 Apr 2016 04:02:21 GMT
https://trac.sagemath.org/ticket/9888#comment:2
https://trac.sagemath.org/ticket/9888#comment:2
<p>
I just tried the timings again:
</p>
<pre class="wiki">sage: sage: M1 = Matrix([[randrange(3^20) for i in range(100)] for j in range(100)])
sage: sage: M2 = Matrix([[randrange(3^20) for i in range(100)] for j in range(100)])
sage: sage: timeit("M3 = M1 * M2")
125 loops, best of 3: 5.62 ms per loop
sage: sage: R = Integers(3^20)
sage: sage: M1 = Matrix([[R.random_element() for i in range(100)] for j in range(100)])
sage: sage: M2 = Matrix([[R.random_element() for i in range(100)] for j in range(100)])
sage: sage: timeit("M3 = M1 * M2")
5 loops, best of 3: 530 ms per loop
</pre><p>
so now the discrepancy is up to a factor of 100!
</p>
<p>
My recollection is that lifting the multiplication up to Z is in fact the correct algorithmic approach. In practice, this hands the problem off to FLINT, where (in this size range) the multiplication is done multimodular.
</p>
TicketkedlayaWed, 17 Aug 2016 01:08:23 GMT
https://trac.sagemath.org/ticket/9888#comment:3
https://trac.sagemath.org/ticket/9888#comment:3
<p>
See <a class="new ticket" href="https://trac.sagemath.org/ticket/12177" title="enhancement: Prime slicing for matrix multiplication (new)">#12177</a> for a related discussion.
</p>
Ticketaly.deinesSun, 22 Oct 2017 18:32:02 GMTkeywords set
https://trac.sagemath.org/ticket/9888#comment:4
https://trac.sagemath.org/ticket/9888#comment:4
<ul>
<li><strong>keywords</strong>
<em>sd90</em> added
</li>
</ul>
TicketkedlayaTue, 24 Oct 2017 04:22:51 GMT
https://trac.sagemath.org/ticket/9888#comment:5
https://trac.sagemath.org/ticket/9888#comment:5
<p>
There appears to be special-purpose code using Linbox for modulus up to 2<sup>23</sup> in <code>sage/matrix/matrix_modn_dense_double.pyx</code> and <code>sage/matrix/matrix_modn_dense_float.pyx</code>. To handle this issue, it would be best to create a file <code>sage/matrix/matrix_modn_dense.pyx</code> in which we create the class <code>Matrix_modn_dense</code> with a special <code>_mul_</code> method. But we should make sure not to create a regression by disconnecting the existing code for smaller moduli.
</p>
Ticket