conv a matrix multiple times

Hello

I have a rectangular matrix and i want to convolve it to some power of that matrix times. e.g.

a = [1 1 0; 1 0 1]^5 

convolve the 1st row with the 1st row 5 times and then the row with the 2nd row 5 times.

Any help!

Answer 1

[Bruno Luong]

a1 = [1 1 0; 
      1 0 1]; % rand(2,3);
p = 5; % power
[m,n] = size(a1);

%% Method 1, straighforward double for-loops
ap = a1;
for p=2:p
    temp = zeros(m,n+size(ap,2)-1);
    for i=1:m
        temp(i,:) = conv(a1(i,:),ap(i,:));
    end
    ap = temp;
end
ap

%% Method 2 single for-loop
ap = a1;
i = 0:n-1;
k = n;
A1 = reshape(a1,[m 1 n]);
for p=2:p
    c = i+(1:k)';
    [r,c] = ndgrid(1:m,c(:));
    ap = A1.*ap;
    k = n+k-1;
    ap = accumarray([r(:) c(:)], ap(:), [m, k]); 
end
ap

You might try to improve by using a "smart" of power raising, by using the binary decomposition of p.

[tanveer haq]

Bruno Luong thanks it works.

[Bruno Luong]

Just for fun here is the code with binary decomposition of p.

It should have less computational intensive for very large p (complexity ~O(log(p)) instead of O(p)). However in my test it's slower than simple for-loop, possibly because involve more memory copying.

a1 = rand(10,3);
p = 32; % power

[m,n] = size(a1);
q = nextpow2(p+1)-1;
a2q = a1;
ap = ones(m,1);
for j = 0:q
    if bitand(2^j,p)
        temp = zeros(m,n+size(ap,2)-1);
        for i=1:m
            temp(i,:) = conv(a2q(i,:),ap(i,:));
        end
        ap = temp;
    end
    if j==q
        break
    end
    n = 2*size(a2q,2)-1;
    temp = zeros(m,n);
    for i=1:m
        temp(i,:) = conv(a2q(i,:),a2q(i,:));
    end
    a2q = temp;
end
ap