How to avoid repeated computation when the result is a symmetric matrix?

Hi all,

When obtaining a symmetric matrix, we know that we only need to compute and store the elements of upper triangular part. Is there a way to only perform these computations related to the upper triangular part, such that the total number of computation can be reduced by almost half?

Check this example:

clear; clc;
a = rand(5, 1);
b = rand(5, 1);
c = rand(5, 1);

x = {a b c};
xtx = zeros(3, 3);

for i = 1:3
    for j = 1:3

          pass = x{i}' * x{j};
          xtx(i, j) = xtx(i, j) + pass;

    end
end

'xtx' is symmetric, but the for loop here computed all elements. Total number of vector products is 9, while we know only 6 products are really needed. If the number of computations is large, then the saving can be dramatic. So how can we solve this?

Many thanks!

[Adam]

When using a for loop it should simply be a case of the inner loop running as

for j = (i+1):3

and then updating both xtx( i, j ) and xtx( j, i ).

For a more general solution where a vectorised approach is used it is less simple though and I'll leave that to someone else!

[Xh Du]

Hi Adam,

I tested your approach does not compute the diagonal line, i.e. when i = j.

[Xh Du]

so for i = j, the inner loop should be:

for j = i:3

[Adam]

I started out with that and changed it. You can just calculate the diagonal separately, but I guess j = i:3 is fine after all.

Answer 1

[Xh Du]

Guess answer is in the comment, credit: Adam.

https://uk.mathworks.com/matlabcentral/answers/332568-how-to-avoid-repeated-computation-when-the-result-is-a-symmetric-matrix#comment_441260