Shift columns of a matrix with different values

Hi,

first of all: I know that my question is not a really new one, however, I do not fully understand some of the solutions proposed in other threads, so I hope someone can help me out. I want to shift rows of a matrix by different amounts. A similiar question was asked here:

https://de.mathworks.com/matlabcentral/answers/111673-how-to-shift-rows-in-a-matrix-by-different-values-e-g-line-1-n-spots-line-2-m-spots-and-so-on-wi

The solution suggested by Azzi Abdelmalek in this thread works for me, but I would like to know if the bsxfun()-based approach by Andrei Bobrov, also suggested in this thread, is faster. Unfortunately I am not able to re-implement his code...

This Code shows what I want to do:

A = [10, 12, 14, 11;
     8 , 10, 13, 10;
     7 ,  8, 12,  8;
     6 ,  7, 10,  7;
     5 ,  6,  8,  6;
     3 ,  5,  7,  5;
     1 ,  3,  6,  3];

ShiftVector = -[0,1,3,1];

origStart = abs(max(ShiftVector))+1;
origEnd   = origStart + size(A ,1) - 1;

B = [zeros(abs(max(ShiftVector)),size(A,2)); ...
    A; ...
    zeros(abs(min(ShiftVector)),size(A,2))];

out=cell2mat(arrayfun(@(x) circshift(B(:,x),[ShiftVector(x) 1]),(1:numel(ShiftVector)),'un',0));


shiftedMatrix = out(origStart:origEnd,1:size(A,2))

The shifted Matrix is:

shiftedMatrix =

    10    10    10    10
     8     8     8     8
     7     7     7     7
     6     6     6     6
     5     5     0     5
     3     3     0     3
     1     0     0     0

I dont want a circular shift of each row but want to append zeros, to fill each shifted rows, as it can be seen in the example above.

I would like to know if there is a faster alternative on how this could be implemented. As I said before Andrei Bobrov proposed a bsxfun()-based solution to a similar problem, but I do not understand how bsxfun could help me out here...

I would be very grateful for any suggestions!

[Adam Danz]

You said Azzi's solution works for you, which uses circshift, but then you said you want to circularly shift each row. That's confusing.

[Marvin H.]

Well, I don't want to shift my original data so that the samples at the beginning of the matrix are shifted circularly to the end of the matrix. Instead, I want those entries at the end of the matrix to be filled up with zeroes as it can be seen in the example...

The code above uses the circshift command, but I artificially prevent that the data appears at the end of the matrix by zeropadding the matrix at the beginning and cropping the matrix "out" to the original size of matrix "A" at the end.

The code does what I want, but I am looking for a faster version.... Is it clearer now what I mean?

[Adam Danz]

I see... I removed my answer for now. Maybe I'll have time to give it another hack later.

[Marvin H.]

The correct question would have been: How to shift columns of a matrix with different values...

[Adam Danz]

Maybe I still don't understand the question because the solutions in the link you referred to are circularly shifting each row by different amounts but the example you gave and the solution the skillful Matt J gave seem to be doing something else.

[MD Rakib]

function y=circshift (x,M)
    if abs (M)>length (x)
    M=rem (M,length(x));
    end
    if M<0
    M=M+length(x);
    end
    y=[x(M+1:length(x))x(1:M)];
    function y = circonv(x1,x2)
    L1=length(x1);
    L2=lenth(x2);
    if L1=L2,error(('the sequence with different length'));
    end
    y=zeros(1,L1);
    x2tr=[x2(1)x2(L2:-1.2)];
    for 1=1:L1
    sh=circshift(x2tr,1-k);
    h=x1,*sh;
    y(k)=sum(h);
end

What is the meaning of the command “rem” in above function “circshift”?  What are the function of the function “circshift” and “circonv”?  Write the program to realize the Circular shift M samples of the sequence x[n]={0,1,2,3,4,5,6,7,8,9}.

Answer 1

[Adam Danz]

Method 1: indexing with rem

This method shifts values rightward in each row of the nxm matrix A by the amounts specified in vector randShift of length n.

% Create demo data
A = (1:4).*ones(6,1)

A = 6×4

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

randShift = [0 1 2 3 4 5]

randShift = 1×6

0 1 2 3 4 5

% shift values in rows of A by the amounts in randShift
randShiftIdx = randShift(:) + (1:size(A,2)).*ones(size(A,1),1);
r = rem(randShiftIdx, size(A,2));
ri = r + (r==0)*size(A,2) + (0:size(A,2):numel(A)-1)';
out = zeros(size(A'));
out(ri) = A;
out = out'

out = 6×4

1 2 3 4 4 1 2 3 3 4 1 2 2 3 4 1 1 2 3 4 4 1 2 3

Method 2: using circshift

Compare to using circshift direclty within a loop which is the fast implementation.

out2 = A;
for i = 1:size(A,1)
    out2(i,:) = circshift(out2(i,:),randShift(i)); 
end
isequal(out, out2) % Confirm that outputs match between methods 1 & 2

ans = logical
   1

Method 3: using bsxfun with rem

This is Andrei Bobrov's solution, modified to accept arrays of any size.

r2 = rem(randShift(:),size(A,2));
c = [A,A];
out3 = c(bsxfun(@plus,bsxfun(@plus,size(A,2) - r2,0:size(A,2)-1)*size(A,1),(1:size(A,1))'));
isequal(out, out3) % Confirm that outputs match between methods 1 & 3

ans = logical
   1

Compare timing

Each method was repeated 10000 times using the same inputs. All outputs were suppressed and unneccessary lines like isequal were removed. The median times are compared below.

• Method 1 vs 2: Method 2 was 1.2 x faster.
• Method 1 vs 3: Method 1 was 1.6 x faster.
• Method 2 vs 3: Method 2 was 1.4 x faster.

Conclusion: circshift within a loop is fastest. Second place is method 1.

Notice that Azzi Abdelmalek's implementation of circshift is within arrayfun and uses cell2mat. That combination of functions condenses the code into 1 line but it's slower than performing the same computations within a loop.

[Marvin H.]

Thank you very much!!

Answer 2

[Matt J]

A = [10, 12, 14, 11;
     8 , 10, 13, 10;
     7 ,  8, 12,  8;
     6 ,  7, 10,  7;
     5 ,  6,  8,  6;
     3 ,  5,  7,  5;
     1 ,  3,  6,  3];

ShiftVector = -[0,1,3,1];


[m,n]=size(A);
J=repmat(1:n,m,1);

Inew=(1:m).'+ ShiftVector;
idx=(1<=Inew) & (Inew<=m);

shiftedMatrix=accumarray([Inew(idx),J(idx)], A(idx),[m,n])

shiftedMatrix = 7×4

10 10 10 10 8 8 8 8 7 7 7 7 6 6 6 6 5 5 0 5 3 3 0 3 1 0 0 0

[Marvin H.]

Thanks, your code works.

I will go for the for-loop / circshift combination suggested by Adam Danz, because it is currently the fastest solution.

Answer 3

[Matt J]

A = [10, 12, 14, 11;
     8 , 10, 13, 10;
     7 ,  8, 12,  8;
     6 ,  7, 10,  7;
     5 ,  6,  8,  6;
     3 ,  5,  7,  5;
     1 ,  3,  6,  3];
ShiftVector = -[0,1,3,1];
[m,n]=size(A);

mask=(1:m).'<=(m+ShiftVector);

shiftedMatrix = mask.*round(ifft(fft(A) .* exp(-2i*pi/m*(0:m-1).'*ShiftVector))  )

shiftedMatrix = 7×4

10 10 10 10 8 8 8 8 7 7 7 7 6 6 6 6 5 5 0 5 3 3 0 3 1 0 0 0