Optimize RAM cost by only storing upper triangular part of a symmetric matrix?

Hi all,

I have some symmetric (almost dense) matrices which I wish to store only the upper triangular part such that I can optimize the usage of RAM. I did some experiments in MATLAB:

>> testa = rand(1000);
>> vsize(testa)
% -------------------------
%    8000000    8000000 B *   testa = 2:1000x1000:double
>> testb = triu(testa);
>> testb = sparse(testb);
>> vsize(testb)
% -------------------------
%    8016008    8016008 B *   testb = 2:1000x1000:double.sparse

We can see that after triu and sparse, storage even increased. I know that when store sparse matrix, each entry cost 8 bytes, storing x-y coordinates cost 8+8 = 16 bytes, so each entry costs 3*8 = 24 bytes, Now that in testb only half number of elements are stored, therefore the cost should be 24 * 1000 * 1000 / 2 = 12000000 bytes, so why is it 8016008 bytes in this case?

Is there a way, say I tell MATLAB that the matrix is symmetric, so I only store half entries, but do not store the x-y coordinates, such that the memory cost is exactly half of the dense matrix?

Thanks!

Answer 1

[Jan]

The memory usage of sparse matrices is explained here: https://www.mathworks.com/matlabcentral/answers/126295-memory-usage-in-sparse-matrix

There is no way to tell Matlab that a matrix is symmetric. Sparse matrices are useful only, if the matrix is really sparse and most elements are 0. For storing a triangular matrix this is not the case.

Some BLAS and LAPACK functions work more efficient for symmetric input. If you want to exploit this, you need to access them on the MEX level. This is not easy and prone to bugs compared to programming in Matlab. The best solution would be to use full matrices and install more RAM. If additional 4GB would be sufficient, this would be a very efficient investment.

PS. I do not get any financial support from the RAM industry. I learned programming on a 1kB ZX81 and squeezed bytes out of the source code by storing numbers as characters. Afterwards I suffered from machine with a maximum of 256kB, then a 192MB laptop and an almost powerfull 1GB WinXP machine. I've learned it on the painful way: nothing can beat real RAM.

[EDITED, 2017-06-24 21:08 UTC] If you can store the matrix in a compact format, all functions to work with the matrix must be adjusted. No operator will work, neither standard algebra nor the optimized BLAS and LAPACK libraries e.g. for matrix multiplication and solvers for matrix equations. Therefore I'm in doubt if saving memory will be useful.

Answer 2

[David Goodmanson]

Hello Xh Du,

The upside here is that if you have several square upper triangular matrices of the same size, you can efficiently store pairs of them in a rectangular matrix:

function r = tris2r(a,b)

% save two square upper triangular matrices a & b, each of size n x n
% as a rectangular matrix r of size (n+1) x n.
% diagonal elements of 'a' are contained in last row of r.

n = size(a,1);
adiag = diag(a).';     % row vector
a(1:(n+1):n^2) = 0;    % zero out the main diag of 'a'
r = [a.'+b; adiag];
end

function [a b] = r2tris(r)

% convert a rectangular matrix r of size (n+1) x n
% to two square upper triangular matrices a & b, each of size n x n.
% diagonal elements of 'a' are contained in last row of r.

n = size(r,2);
adiag = r(end,:);
r(end,:) = [];
b = triu(r);
a = tril(r).';
a(1:(n+1):n^2) = adiag;    % insert the diagonal of 'a' 
end

With a bit more work and computation you can store a single upper triangular matrix in a rectangular matrix of size (n+1) x (n/2) for n even and n x (n+1)/2 for n odd.