id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
9888 matrix multiplication over integer mod ring is slow dmharvey tbd "Sage 4.5.3, 2.6GHz Opteron, Linux
This is ok:
{{{
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
}}}
(That's about 4 times slower than Magma, but I can put up with that, that's a ticket for another day.)
Here is the problem:
{{{
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
}}}
In other words, I can multiply the matrices over R roughly 20x faster by multiplying over Z and then reducing! That's ridiculous!
" defect new major performance sd90 N/A