Scipy/numpy: two dense, one sparse dot product
<p>Let's say we have a matrix <code>A</code> of size <code>NxN</code>, and <code>A</code> is sparse and <code>N</code> is very large. So we naturally want to store is as as scipy sparse matrix.</p>

<p>We also have a dense numpy array <code>q</code> of size <code>NxK</code>, where <code>K</code> is relatively smaller.</p>

<p>How do we most efficiently perform <code>q.T * A * q</code>, where <code>*</code> is matrix multiplication, to obtain a <code>KxK</code> result?</p>

<p>One part of what we want can be done efficiently, that is just <code>A * q</code>, but once you do that you materialize a dense array that you then need to multiply with another dense array.</p>

<p>Any way to do it faster than <code>q.T.dot(A.dot(q))</code>?</p>

<p>So you have</p>

<pre><code>(k,N) * (N,N) * (N,k) =&gt; (k,k)
</code></pre>

<p>One of those dot product results in a dense array; that times another dense is also dense.  With a multiplication like this you quickly loose the sparsity.</p>

<p>If <code>q</code> has a lot of 0s, and you want to preserve the sparse matrix nature of the problem, make <code>q</code> sparse before doing this multiplication.</p>

python arrays numpy matrix scipy