I think you've just described the approach laid out in this document -- http://www.google.com/url?sa=t&source=web&cd=1&ved=0CB8QFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.144.9712%26rep%3Drep1%26type%3Dpdf&ei=WfAJTtr8Ju6FsgKz6cyeAQ&usg=AFQjCNFxQPXXnYw93eBpUknGy2iZJESmHw&sig2=zFxncZg4n7b_mueF4mbGPQ
There's one other trick you could employ -- since the resulting matrix is symmetric, you really only have to bother with half of the multiplications and sums (plus the diagonal). After all, if A*A' = B, then Bij = Bji. So if you only calculate Bij for i <= j, you can flip the matrix to fill in the other half. That means when you're doing your cross product in the mapper phase you've mentioned, you only need to do half the cross multiplications: for(int j = i; j <= i;j++)emit i, j, i*j; Of course this is all based on the assumption that we're multiplying a matrix with itself transposed. On Sun, Jun 26, 2011 at 10:34 PM, Jake Mannix <[email protected]> wrote: > Thus the right approach is transpose first, then do an in-memory "map" (in > parallel) over the rows of the result, outer multiplying each and sending > the rows of this outer product to the "reduce" step, which sums (again in > parallel, since their independent there should be no sychronization cost) > these rows. > > Even though its in-memory, its still classic MapReduce, and well suited to > parallelism (although its a good example of a nicely parallel algorithm > which is *not* "emberassingly parallel" - both the map and reduce are > nontrivial and different). > > Now that I think about it further, *self* multiplication (ie A * A'), where > the entries are all +/- 1 lends itself to even more optimization chances: > the rows of the outer product matrix (produced in the Map phase, for each > column of the input matrix) are all equal to either that row, or its > negative. Calculating these is just changing 16 signs, not 256 > multiplications. > > -jake > > On Jun 26, 2011 6:51 PM, "Ted Dunning" <[email protected]> wrote: > > And going down teh columns in a sparse matrix could do this to you. > > On Sun, Jun 26, 2011 at 6:40 PM, Jake Mannix <[email protected]> > wrote: > > On Sun, Jun 26, 2011... >
