# Count number of 1's in $\textbf{u}\textbf{v}^T$

I am seeking for an efficient algorithm to count the number of 1's in the outer product $\textbf{u}\textbf{v}^T$, where $\textbf{u}$ and $\textbf{v}$ are both binary column vectors.

The dimension of $\textbf{u}$ is about 50, and the dimension of $\textbf{v}$ is about 20,000. I have a loop of about 1,000,000 iterations, in each iteration, one (and only one) element of both $\textbf{u}$ and $\textbf{v}$ are randomly chosen and are overwritten with 0 or 1 (could be the same as the old value).

I would like to know something in MATLAB that could finish this task on a desktop machine (no parallel, no cluster) within 3 seconds (or 5 seconds, depend on hardware). I've tried $bsxfun()$, $gpuArray()$, and all those tricks I know of, but without luck.

-
Sorry, I made a mistake. It was not for the whole matrix $\textbf{u}\textbf{v}^T$, but for a pre-defined index subset, say $\sum_{(i,j) \in S} M(i,j)$, where $M=\textbf{u}\textbf{v}^T$ and $S$ is a pre-defined subset. –  David Tan Nov 28 '12 at 18:33

If both $u,v$ are 0-1 vectors, the number of ones in $uv^T$ is the no. of ones in $u$ times the no. of ones in $v$. So, how about sum(u)*sum(v)?

Edit: That doesn't mean you should really sum up $u$ and $v$ inside the loop, because even MATLAB's sum function is still very slow. Instead, you may keep track of count $r=$ no. of ones in $u$ and the count $c=$ no. of ones in $v$. For example, in each iteration, if the $i$-th element of $u$ is selected and it switches from 0 to 1, increment $r$ by $1$. Update $c$ in a similar manner. Now the number of ones is computed as $r\times c$ at the end of each iteration. On my 4-year old PC with the antique MATLAB 5.3 installed, one million iterations cost only 7 seconds.

-
Say $S=\{(1,2),(1,3),(2,1)\}$, $\textbf{u}=(1,0,0,1)^T,\textbf{v}=(1,1,0,0)^T$, the outer product is $(1100;0000;0000;1100)$. So the sum I wanted is $1+0+0=1$. Next, if $\textbf{u}(3)$ is flipped to 1, we end up with $(1100;0000;1100;1100)$, the sum is still $1+0+0=1$ (but the matrix changed). Note, the subset $S$ will not change during the whole process. –  David Tan Nov 28 '12 at 18:44
@DavidTan: In your modified problem, you are essentially counting the no. of 1s in a (sparse?) submatrix $S$. since $S$ is merely a list of points without special structure, I don't think one can make a counting procedure much faster than a brute force count. But surely don't take my word for it. You may pose a new question to the forum, and see if the others can help. –  user1551 Nov 29 '12 at 11:40