Optimize RAM cost by only storing upper triangular part of a symmetric matrix?
11 次查看(过去 30 天)
显示 更早的评论
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!
0 个评论
回答(2 个)
Jan
2017-6-21
编辑:Jan
2021-4-24
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.
0 个评论
David Goodmanson
2017-6-24
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.
0 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Performance and Memory 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!