MATLAB: vectorize for-loop containing circshift
I have the following for-loop that I'd like to vectorize. However, inside the for-loop I use circshift. Is there a way to perform the for-loop using vectorization, or at least optimize it? It runs very slowly as strt, stop and M increase their size.
indx = 0; M = magic(16); v = M(:,1); strt=-5; stop=+5; result = zeros(4, length(strt:stop), 4); for ii=strt:stop tmp = circshift(M, [0 ii])*v; tmp = tmp/norm(tmp); indx = indx+1; result(:, indx, :) = reshape( tmp(:,1), 4,4); end
Shifting that huge 2D array, M with circshift would surely be expensive. So, one trick could be to shift around the 1D array v instead in the other direction and keep M as it is. So, we need just one edit to replace :
circshift(M, [0 ii])*v with M*circshift(v,-ii).
The runtimes for M as (2500 x 2500) sized array with the original and proposed approaches at my end were -
----------------------- With Original approach Elapsed time is 0.803823 seconds. ----------------------- With Proposed approach Elapsed time is 0.137444 seconds.
When you increase the size of M, the function circshift becomes the most time consuming part of your code. This time is increasing with the size.
One helpful step is to change circshift(M, [0 ii])*v to M*circshift(v,-ii). Note that they produce the same tmp, but the second one deals with v which is just one column of M.
This can be represented as a 2D convolution , so this code tested in Octave, for Matlab some changes needed that explained in the comments:
%temp created however order of column reversed relative to your 'tmp' temp=conv2([M M(:,1:10)] , circshift(flipud(v).', [0 , 5]),'valid'); %only availabe in Octave. Norm of columns computed . In Matlab use for loop to compute norm of each column nrm=norm(temp,'cols'); %divide temp by norm temp = bsxfun(@rdivide,temp,nrm); % The result. Order of slices reversed result = reshape(temp,[4,4,size(temp,2)])