ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 12 Nov 2011 04:22:49 -0600Speeding up matrix multiplication?http://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/I'm currently trying write code to compute with overconvergent modular symbols. In iterating a Hecke operator, the key (i.e. most time consuming) operation that is performed tons of times is simply taking the product of a large dense matrix say $M$ with a vector $v$, both with integral entries.
More precisely, let $p$ be a (relatively small) prime (think $p=11$) and $N$ some integer (think 100). I have an $N$ by $N$ matrix and am interested in quickly computing the product $M \cdot v$ modulo $p^N$.
I am simply using the intrinsic SAGE command of multiplying a matrix by a vector, and I was surprised to see that working with matrices over ${\bf Z}/p^n{\bf Z}$ was much (i.e. 10 times) slower than working with matrices over ${\bf Z}$.
My question: is there a faster way to do this computation than using SAGE's intrinsic matrix times a vector command over ${\bf Z}$?
Fri, 04 Nov 2011 11:46:03 -0500http://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/Answer by William Stein for <p>I'm currently trying write code to compute with overconvergent modular symbols. In iterating a Hecke operator, the key (i.e. most time consuming) operation that is performed tons of times is simply taking the product of a large dense matrix say $M$ with a vector $v$, both with integral entries. </p>
<p>More precisely, let $p$ be a (relatively small) prime (think $p=11$) and $N$ some integer (think 100). I have an $N$ by $N$ matrix and am interested in quickly computing the product $M \cdot v$ modulo $p^N$. </p>
<p>I am simply using the intrinsic SAGE command of multiplying a matrix by a vector, and I was surprised to see that working with matrices over ${\bf Z}/p^n{\bf Z}$ was much (i.e. 10 times) slower than working with matrices over ${\bf Z}$. </p>
<p>My question: is there a faster way to do this computation than using SAGE's intrinsic matrix times a vector command over ${\bf Z}$?</p>
http://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/?answer=12889#post-id-12889Robert -- this could be fixed so it works exactly like you want, but it requires writing some code in Cython, and pretty advanced knowledge of Sage internals. One potential workaround is to simply multiply over ZZ, then reduce the answer, e.g., do something like this:
sage: M = random_matrix(ZZ,100)
sage: v = random_matrix(ZZ,100,1)
sage: timeit('(M*v) % 11^3')
625 loops, best of 3: 631 µs per loop
which beats all the following by a lot:
sage: M = random_matrix(ZZ,100)
sage: v = random_vector(Integers(11^3),100)
sage: timeit('M*v')
125 loops, best of 3: 2.55 ms per loop
sage: M = random_matrix(ZZ,100)
sage: v = random_matrix(Integers(11^3),100,1)
sage: timeit('M*v')
125 loops, best of 3: 4.83 ms per loop
sage: M = random_matrix(ZZ,100)
sage: v = random_vector(ZZ,100)
sage: timeit('(M*v) % 11^3')
125 loops, best of 3: 4.42 ms per loop
Incidentally, "write code to compute with overconvergent modular symbols" is something Ben Lundell and I at UW have been wanting to do in the near future to. Maybe we can coordinate? Email us. Sat, 12 Nov 2011 04:22:49 -0600http://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/?answer=12889#post-id-12889Answer by parzan for <p>I'm currently trying write code to compute with overconvergent modular symbols. In iterating a Hecke operator, the key (i.e. most time consuming) operation that is performed tons of times is simply taking the product of a large dense matrix say $M$ with a vector $v$, both with integral entries. </p>
<p>More precisely, let $p$ be a (relatively small) prime (think $p=11$) and $N$ some integer (think 100). I have an $N$ by $N$ matrix and am interested in quickly computing the product $M \cdot v$ modulo $p^N$. </p>
<p>I am simply using the intrinsic SAGE command of multiplying a matrix by a vector, and I was surprised to see that working with matrices over ${\bf Z}/p^n{\bf Z}$ was much (i.e. 10 times) slower than working with matrices over ${\bf Z}$. </p>
<p>My question: is there a faster way to do this computation than using SAGE's intrinsic matrix times a vector command over ${\bf Z}$?</p>
http://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/?answer=12862#post-id-12862If numerical approximations are good enough for you you can speed things up:
sage: m = random_matrix(ZZ, 100, 100, x=0, y=10^100)
sage: v = random_vector(ZZ, 100, x=0, y=10^100)
sage: timeit('m*v')
125 loops, best of 3: 7.37 ms per loop
this is much faster:
sage: mr = matrix(RDF,m)
sage: vr = vector(RDF,v)
sage: timeit('mr*vr')
625 loops, best of 3: 367 µs per loop
If you supply the code which gives your bottleneck people might be more helpful in optimization ideas.
Sun, 06 Nov 2011 08:24:33 -0600http://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/?answer=12862#post-id-12862Comment by John Palmieri for <p>If numerical approximations are good enough for you you can speed things up:</p>
<pre><code>sage: m = random_matrix(ZZ, 100, 100, x=0, y=10^100)
sage: v = random_vector(ZZ, 100, x=0, y=10^100)
sage: timeit('m*v')
125 loops, best of 3: 7.37 ms per loop
</code></pre>
<p>this is much faster:</p>
<pre><code>sage: mr = matrix(RDF,m)
sage: vr = vector(RDF,v)
sage: timeit('mr*vr')
625 loops, best of 3: 367 µs per loop
</code></pre>
<p>If you supply the code which gives your bottleneck people might be more helpful in optimization ideas.</p>
http://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/?comment=20954#post-id-20954It seems that multiplying matrices over GF(p) is a bit faster, at least if p is small. Can you work over several different small primes and extract the information you need from that?Sun, 06 Nov 2011 18:31:29 -0600http://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/?comment=20954#post-id-20954Comment by Robert Pollack for <p>If numerical approximations are good enough for you you can speed things up:</p>
<pre><code>sage: m = random_matrix(ZZ, 100, 100, x=0, y=10^100)
sage: v = random_vector(ZZ, 100, x=0, y=10^100)
sage: timeit('m*v')
125 loops, best of 3: 7.37 ms per loop
</code></pre>
<p>this is much faster:</p>
<pre><code>sage: mr = matrix(RDF,m)
sage: vr = vector(RDF,v)
sage: timeit('mr*vr')
625 loops, best of 3: 367 µs per loop
</code></pre>
<p>If you supply the code which gives your bottleneck people might be more helpful in optimization ideas.</p>
http://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/?comment=20952#post-id-20952I'll give it a try! Thanks.Mon, 07 Nov 2011 02:34:05 -0600http://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/?comment=20952#post-id-20952Comment by Robert Pollack for <p>If numerical approximations are good enough for you you can speed things up:</p>
<pre><code>sage: m = random_matrix(ZZ, 100, 100, x=0, y=10^100)
sage: v = random_vector(ZZ, 100, x=0, y=10^100)
sage: timeit('m*v')
125 loops, best of 3: 7.37 ms per loop
</code></pre>
<p>this is much faster:</p>
<pre><code>sage: mr = matrix(RDF,m)
sage: vr = vector(RDF,v)
sage: timeit('mr*vr')
625 loops, best of 3: 367 µs per loop
</code></pre>
<p>If you supply the code which gives your bottleneck people might be more helpful in optimization ideas.</p>
http://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/?comment=20955#post-id-20955Thanks parzan. Unfortunately I need an exact computation. More precisely, I'm working modulo p^N where p^N is around 10^100. I'll edit my question accordingly. About supplying code, the computation really boils down to the one line M*v applied again and again where M is the large matrix, and v the vector.Sun, 06 Nov 2011 15:51:23 -0600http://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/?comment=20955#post-id-20955