Multiplication of a Sparse Matrix With Diagonal Matrices

I have a sparse m x m square matrix L (which is actually a Laplacian matrix of a large graph) and an m x1 vector d. I want to create a diaognal matrix D whose diagonal is populated with the entries in d and then generate

normL = D * L * D

Currently, I am creating a sparse diaognal matrix as

D = spdiags(d, 0, m, m)

and then I use D * L * D.

I wonder whether there is a more efficient way to do this given that the (i, j)-th elements of normL and L are related by

normL(i, j) = D(i) * D(j) * L(i, j).

Thank you very much.

Answer 1

[Arjun]

Hi,

I see that you are seeking an efficient method to compute "normL" using a Laplacian matrix (L) and a diagonal matrix (D).

The efficient method for computing “normL = D * L * D”, where “L” is a sparse Laplacian matrix and “D” is a diagonal matrix formed from a vector “d”, involves leveraging element-wise operations to bypass the need for full matrix multiplications. Instead of constructing the diagonal matrix “D”, the method calculates the outer product “d * d' ”, yielding a matrix where each element is the product of corresponding elements from “d”. This outer product is then multiplied element-wise with the sparse matrix “L”, effectively computing each element of “normL(i,j) = D(i) * D(j) * L(i,j)”.

Kindly refer to the code below for better understanding:

% Parameters
m = 5; % Size of the matrix

% Generate a random sparse Laplacian matrix L
% For simplicity, let's create a random sparse symmetric matrix
A = sprand(m, m, 0.3); % Sparse random matrix with 30% density
L = A + A'; % Make it symmetric
L = L - diag(sum(L, 2)); % Ensure it's a Laplacian matrix

% Generate a random vector d
d = rand(m, 1);

% Compute normL using the efficient method
dOuter = d * d'; % Outer product
normL = L .* dOuter; % Element-wise multiplication
disp(normL);

This method avoids the need to explicitly construct a diagonal matrix and perform full matrix multiplication operations, thereby being more efficient compared to the traditional method.

I hope it helps!

[Kamal Premaratne]

Thank you so much Arjun. It has been over 4 years since I posted the question, and yet I am so glad that you responded. And yes, your answer helps tremendously. Thanks again.

[Arjun]

I am very thankfull that you took time to come back and appreciate my effort!