How to reduce running time of diagonal matrix multiplication with full matrix in Matlab?

9 views (last 30 days)
I need to calculate a matrix multiplication that , where B is a full matrix with and D is a digonal matrix with .The computational complexity is
Acturally, if the matrix D is a full matrix, the computational complexity will be .
I recorded the running time for both cases in matlab, and find that the running time and time complexity are not consistent, how can I speed it up? I want to use less time to calculate the first case compared with the second case.
Thanks.
  2 Comments
Chunru
Chunru on 28 Jul 2022
The simplest case is for D=I. Then . The complexity for this matrix multiplication is rather than .
For full matrix D, the complexity is .
For diagonal D, the complexity is .

Sign in to comment.

Accepted Answer

Chunru
Chunru on 28 Jul 2022
Edited: Chunru on 28 Jul 2022
n = 2000; d=500;
B = randn(d, n);
dv = randn(n, 1);
D = diag(dv);
% Normal
tic
A = B*D*B';
toc
Elapsed time is 0.052677 seconds.
% Speed up 1
tic
C = B*(dv.*B');
toc
Elapsed time is 0.012931 seconds.
% Speed up 2
tic
E = (B.*dv')*B';
toc
Elapsed time is 0.012015 seconds.
A(1:5, 1:5)
ans = 5×5
6.0809 11.2463 -58.6430 -66.3057 -24.0124 11.2463 -49.0177 52.5213 23.6997 18.0264 -58.6430 52.5213 42.9952 29.0237 23.4184 -66.3057 23.6997 29.0237 -44.6983 -0.1757 -24.0124 18.0264 23.4184 -0.1757 -61.5623
C(1:5, 1:5)
ans = 5×5
6.0809 11.2463 -58.6430 -66.3057 -24.0124 11.2463 -49.0177 52.5213 23.6997 18.0264 -58.6430 52.5213 42.9952 29.0237 23.4184 -66.3057 23.6997 29.0237 -44.6983 -0.1757 -24.0124 18.0264 23.4184 -0.1757 -61.5623
E(1:5, 1:5)
ans = 5×5
6.0809 11.2463 -58.6430 -66.3057 -24.0124 11.2463 -49.0177 52.5213 23.6997 18.0264 -58.6430 52.5213 42.9952 29.0237 23.4184 -66.3057 23.6997 29.0237 -44.6983 -0.1757 -24.0124 18.0264 23.4184 -0.1757 -61.5623

More Answers (0)

Categories

Find more on Operating on Diagonal Matrices in Help Center and File Exchange

Products


Release

R2019b

Community Treasure Hunt

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

Start Hunting!