1
$\begingroup$

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.

  • 0
    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.2012-11-28

1 Answers 1

4

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.

  • 0
    @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.2012-11-29