Sum over all diagonals in lower matrix

Hi, I have a matrix which I will take the sum over the diagonals in the lower matrix. So for example my matrix A=rand(4,4); the result I want is following vector

P=[sum(diag(A)); sum(diag(A,-1)); sum(diag(A,-2)); sum(diag(A,-3))]

My matrix is much larger, how can this be done without looping?

Answer 1

[Jan]

Why do you prefer a solution without a loop?

function speedtest
A = rand(1000, 1000);
tic
for k = 1:20
  P = test1(A);
end
toc

tic
for k = 1:20
  P = test2(A);
end
toc

function P = test1(A)
rowdest = toeplitz(1:size(A, 1), [1, repelem(size(A, 1)+1, size(A, 2)-1)]);
P = accumarray(rowdest(:), A(:));
P = P(1:end-1);

function P = test2(A)
n = size(A, 1);
P = zeros(n, 1);
for k = 1:n
   P(k) = sum(diag(A, 1-k));
end

Matlab 2016b/64, Win7, Core2Duo:

 Elapsed time is 1.139792 seconds.  % Toeplitz
 Elapsed time is 0.182293 seconds.  % Loop

I could not estimate, if the overhead for the loops or for creating the large index matrix are more expensive. But this short test seems, like the loop is efficient.

[Andrei Bobrov]

Hi Jan! +1.

Elapsed time is 0.902673 seconds. % toeplitz
Elapsed time is 0.206180 seconds. % loop for..end and diag
Elapsed time is 0.472602 seconds. % spdiags

on my laptop

[Jan]

@Lenovo: I share your preference for smart commands and clever solutions. This dull loop does not really satisfy me. But it is simple and fast.

[Guillaume]

The dull loop is also the simplest to understand, which I'd actually value over speed and conciseness. It's immediately clear what it does without having to do any mental gymnastic.

Another version of the loop, in my opinion even clearer (albeit probably slightly slower):

arrayfun(@(d), sum(diag(A, 1-d)), 1:size(A, 1))

Answer 2

[Guillaume]

A = reshape(1:30, 5, 6) %demo data

rowdest = toeplitz(1:size(A, 1), [1, repelem(size(A, 1)+1, size(A, 2)-1)]);
P = accumarray(rowdest(:), A(:));
P = P(1:end-1)

[Stephen23]

Or without repelem:

>> A = randi(9,4,4)
A =
     8     1     6     8
     4     2     1     1
     3     9     3     1
     4     9     4     2
>> X = toeplitz(2:1+size(A,1),[2,ones(1,size(A,2)-1)]);
>> V = accumarray(X(:),A(:));
>> V = V(2:end)
V =
    15
    17
    12
     4

[Jan]

@Guillaume: Your solution is nice and Matlabish. I could not predict, if it is faster or slower than a simple loop, therefore I tried it.

After the measurement, I assume the creation of the large index matrix needs more time than the loop overhead costs.

Answer 3

[Andrei Bobrov]

P = sum(spdiags(A.',0:size(A,1)-1)).';

[Orongo]

Given it is a matrix manipulation and it is Matlab, I'm convinced there are clever solutions out there handling this type of calculations.

spdiags looks promising, however if a diagonal is zero I must have it return as zero so number of rows in the result matches number of rows in the matrix.

[Andrei Bobrov]

[EDIT]

I'm corrected. Please read about spdiags.