20 views (last 30 days)

Show older comments

I have a very big (n>1000000) sparse symmetric positive definite matrix A and I want to multiply it efficiently by a vector x. Only the lower triangular of matrix A is stored with function "sparse". Is there any function inbuilt or external that anyone knows of that takes as input only the lower triangular and performs the complete operation Ax without having to recover whole A (adding the strict upper triangular again)?

Thank you very much,

Jan

Jan
on 24 Apr 2021

Edited: Jan
on 24 Apr 2021

Plese check if this is efficient in your case:

A = rand(5, 5);

A = A + A'; % Symmetric example matrix

B = tril(A); % Left triangular part

x = rand(5, 1);

y1 = A * x;

y2 = B * x + B.' * x - diag(B) .* x;

y1 - y2

I assume that Matlab's JIT can handle B.' * x without computing B.' explicitly. Alternative:

y2 = B * x + B.' * x - diag(diag(B)) * x;

Clayton Gotberg
on 24 Apr 2021

If is a symmetric matrix and is the lower triangular part of the matrix and is the upper triangular part of the matrix:

where the diagonal function only finds the diagonal elements of . This is because of a few relations:

To save time and space on MATLAB (because the upper triangular matrix will take up much more space), take advantage of the relations:

To get:

Now, the MATLAB calculation is

A_times_x = A_LT*x+(x.'*A_LT).'+ diag(A_LT).*x;

This should only perform transposes on the smaller resultant matrices.

Clayton Gotberg
on 24 Apr 2021

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

Start Hunting!