Calculating diagonal elements of a matrix product without a loop or redundant calculations

20 次查看（过去 30 天）
Earl
Earl 2012-3-11
I have a problem wich invovles calculating the product of the ith row of a matrix, say F, and another matrix, say B, and then multiplying again by the ith row of F as a column (for each row of F). Basically, something like this:
A = [];
for i = 1:length(F)
A(i) = F(i,:)*B*F(i,:)';
end
This code works, but it is not ideal because it uses a loop rather than Matlab's native interpreted language. The following code also achieves the same result:
A = diag(F*B*F');
The problem here is that it is calculating all the elements of F*B*F', and then only selecting the diagonal elements (which is all I ultimately want). So this is also extremely inefficient (especially for larger matrices F and B) because there are many redundant calculations.
Is there a way to get this result without using loops or redundant calculations, for example, using element-wise algebra (i.e. using the ".*" operator)? I tried F*B.*F' but this does not give the same result.
Thanks.
  1 个评论
Daniel Shub
Daniel Shub 2012-3-11
One can no longer simply say that loops are slow in MATLAB. A lot of improvements have happened in the past 10(?) years. Even the concept of preallocate or die is less rigid (although I would preallocate your A here instead of initializing it to empty).

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Oleg Komarov
Oleg Komarov 2012-3-11
% Example inputs
F = rand(10);
B = rand(10);
out1 = sum(F*B.*F,2); % Elementwise
out2 = diag(F*B*F');
isequal(out1,out2)
However I don't see an improvement in the timing, it could actually be the case that diag(F*B*F') doesn't calculate all the cross products.

更多回答（1 个）

Earl
Earl 2012-3-11
Thanks for the reply Oleg. Yes, I think this is the answer I am after, although I'm not entirely sure what the sum() function is doing here.
And you are right about the timing - there does not appear to be any significant difference:
F = rand(1000);
B = rand(1000);
tic; out1 = sum(F*B.*F,2); toc; % Elementwise
tic; out2 = diag(F*B*F'); toc;
I get a difference of about 0.03 seconds. However, I'm fairly sure Matlab does actually compute the off-diagonals because:
F = rand(1000);
B = rand(1000);
tic; out2 = diag(F*B*F'); toc;
tic; out2a = F*B*F'; out2b = diag(out2a); toc;
gives almost the same computation time. This is a little puzzling because I would have thought the redundant calculations to be of the order n squared where n is the dimensions of F*B*F'. But apparently it makes little difference.
Thanks again for the insight.
  3 个评论
显示 1更早的评论
Jan
Jan 2012-3-12
I get this under Win7/Matlab 2009a/64:
tic; out1 = sum(F*B.*F,2); toc;
>> Elapsed time is 0.165536 seconds.
tic; out2 = diag(F*B*F'); toc;
>> Elapsed time is 0.288225 seconds.
Oleg Komarov
Oleg Komarov 2012-3-12
Average on 100 iterations and size 1000x1000, Win7 R2012a 64bit:
out1 = sum(F*B.*F,2): 0.04818
out2 = diag(F*B*F') : 0.08834

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Linear Algebra 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by