Thread Subject: Vectorization

Hi all --

I am wondering if it is possible to eliminate the loop in the
following piece of code:

for i=1:K
  W(i,:) = Q(i,:)*V(:,P(i,:));
end;

(that is: each row i of the result is computed by multiplying ith row
of matrix Q by a permutation of columns of V specified by the i'th row
of P).

Here Q is a KxK square matrix; and all other matrices are KxN. P is an
existing index matrix containing indices into columns of V.

I've tried a few things but so far have not had too much success... :(

laxxy <laxyfoxx@gmail.com> wrote in message <8d98157c-ab47-40cb-8e4f-af119371a0db@h8g2000yqm.googlegroups.com>...
> Hi all --
>
> I am wondering if it is possible to eliminate the loop in the
> following piece of code:
>
> for i=1:K
> W(i,:) = Q(i,:)*V(:,P(i,:));
> end;
>
> (that is: each row i of the result is computed by multiplying ith row
> of matrix Q by a permutation of columns of V specified by the i'th row
> of P).
>
> Here Q is a KxK square matrix; and all other matrices are KxN. P is an
> existing index matrix containing indices into columns of V.
>
> I've tried a few things but so far have not had too much success... :(

W=Q*V(repmat((1:K)',1,N)+(P-1)*K);

HTH
Yi

> > I am wondering if it is possible to eliminate the loop in the
> > following piece of code:
>
> > for i=1:K
> >   W(i,:) = Q(i,:)*V(:,P(i,:));
> > end;
>
> > (that is: each row i of the result is computed by multiplying ith row
> > of matrix Q by a permutation of columns of V specified by the i'th row
> > of P).
>
> W=Q*V(repmat((1:K)',1,N)+(P-1)*K);

Thanks!
But this is not quite the same though: in your solution each row of
the V(...) is permuted differently; but the i'th iteration of the loop
computes the same permutation on all rows of V which is specified
given by P(i,:)...

On 4 Jul, 22:24, laxxy <laxyf...@gmail.com> wrote:
> Hi all --
>
> I am wondering if it is possible to eliminate the loop in the
> following piece of code:
>
> for i=1:K
>   W(i,:) = Q(i,:)*V(:,P(i,:));
> end;
>
> (that is: each row i of the result is computed by multiplying ith row
> of matrix Q by a permutation of columns of V specified by the i'th row
> of P).
>
> Here Q is a KxK square matrix; and all other matrices are KxN. P is an
> existing index matrix containing indices into columns of V.
>
> I've tried a few things but so far have not had too much success... :(

What about

W(1:K,:) = Q(1:K,:)*V(:,P(1:K,:));

Rune

W = Q*V;
W = W(bsxfun(@plus,(1:K)',(P-1)*K))

% Bruno

laxxy <laxyfoxx@gmail.com> wrote in message <491153fb-0184-4438-997d-cacf25797dea@i6g2000yqj.googlegroups.com>...
> > > I am wondering if it is possible to eliminate the loop in the
> > > following piece of code:
> >
> > > for i=1:K
> > > ? W(i,:) = Q(i,:)*V(:,P(i,:));
> > > end;
> >
> > > (that is: each row i of the result is computed by multiplying ith row
> > > of matrix Q by a permutation of columns of V specified by the i'th row
> > > of P).
> >
> > W=Q*V(repmat((1:K)',1,N)+(P-1)*K);
>
> Thanks!
> But this is not quite the same though: in your solution each row of
> the V(...) is permuted differently; but the i'th iteration of the loop
> computes the same permutation on all rows of V which is specified
> given by P(i,:)...

Bruno is right. Instead of permutating before multiplying, it should be after the production. Try the following code:

% prepare some data
K=10;
N=20;
Q=randn(K);
V=randn(K,N);
[Z,P]=sort(V,2); % produce some permutation

% vectorized
Z=Q*V;
Z=Z(repmat((1:K)',1,N)+(P-1)*K);

%original loop
W=zeros(K,N);
for i=1:K
W(i,:) = Q(i,:)*V(:,P(i,:));
end;

%compare difference
norm(W-Z)

% should be very small

HTH
Yi

Very cute -- thanks a lot Yi & Bruno!!

> % vectorized
> Z=Q*V;
> Z=Z(repmat((1:K)',1,N)+(P-1)*K);
>
> %original loop
> W=zeros(K,N);
> for i=1:K
> W(i,:) = Q(i,:)*V(:,P(i,:));
> end;