MATLAB Answers

Symmetric Matrix-Vector Multiplication with only lower triangular stored

19 views (last 30 days)
Jan Marxen
Jan Marxen on 24 Apr 2021
Commented: Jan Marxen on 27 Apr 2021
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

Accepted Answer

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
ans = 5×1
1.0e+-15 * 0 0 -0.4441 0 0
I assume that Matlab's JIT can handle B.' * x without computing B.' explicitly. Alternative:
y2 = B * x + B.' * x - diag(diag(B)) * x;
  6 Comments
Jan Marxen
Jan Marxen on 27 Apr 2021
im sorry for the late reply. I mean that the time cost gets larger.
There are obvious ways to exploit the symmetry of the problem such as doing the multiplication and sum as usual but change i and j index when arriving at the diagonal such that it keeps using the lower triangular elements. But programming this won't be nearly as efficient as Matlabs inbuilt multiplications, even if it exploits the symmetry.
Thank you for the help and the experimenting,
Jan

Sign in to comment.

More Answers (1)

Clayton Gotberg
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.
  7 Comments
Clayton Gotberg
Clayton Gotberg on 24 Apr 2021
I begin to understand why engineers are specifically trained and hired to test software. It's deeply interesting to get this peek into what MATLAB does to ensure I can keep writing ill-considered code.

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!