MATLAB: Symmetric Matrix-Vector Multiplication with only lower triangular stored

matrix multiplication

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

Best Answer

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;

Related Solutions

MATLAB: SVDS– what is the point of using it and is it ever faster than SVD?

Really big means millions by millions. I use the sparse type for the matrix, but still it doesn't seem to speed things up.

I assume the comparison between SVD and SVDS that you're performing is on a scaled down version of this matrix. There is no way a "millions by millions" matrix can be stored in anything but sparse type and there is no way you can be running SVD on a sparse type matrix (it would return an error).

If your tests are based on small scale versions of your actual matrix, we need to ask how small. Definitely the gains in SVDS over SVD won't be seen if your examples are too small, e.g.,

>> N=100; As=speye(N);A=eye(N); tic; svd(A); toc ; tic; svds(A); toc
Elapsed time is 0.001177 seconds.
Elapsed time is 0.006077 seconds.

but there are clearly also examples where svds is better, e.g.,

>> N=5000; As=speye(N);A=eye(N); tic; svd(A); toc ; tic; svds(A); toc
Elapsed time is 47.876229 seconds.
Elapsed time is 0.324260 seconds.

MATLAB: When is eigs profitable in terms of time comparing to eig

There is no clear answer, since this depends on many factors: - Are your matrices dense or sparse, and if they are sparse, how sparse and with what sparsity structure? - Are the eigenvalues clustered closely together?

If we're assuming that all your matrices are dense and nicely conditioned, we can just try it out using random matrices (note that the performance here is also machine-dependent):

 rng default;
 A = randn(n);
 A = A+A';
 B = randn(n);
 B = B*B';
 tic;
 [U, D] = eig(A, B); 
 toc
 tic;
 [U, D] = eigs(A, 1, 'smallestabs');
 toc
 For n = 1000, EIGS is faster:
 Elapsed time is 0.181162 seconds.
 Elapsed time is 0.039232 seconds.
 For n = 200, they take comparable amounts of time:
 Elapsed time is 0.016852 seconds.
 Elapsed time is 0.011491 seconds.
 For n = 100, EIG is faster:
 Elapsed time is 0.004331 seconds.
 Elapsed time is 0.036057 seconds.

Even for sparse matrices, I'd typically use EIG instead of EIGS for n<100.

Best Answer

Related Solutions

MATLAB: SVDS– what is the point of using it and is it ever faster than SVD?

MATLAB: When is eigs profitable in terms of time comparing to eig

Related Question