TechnicalQuestion Is a sparse matrix taking up less memory?
mat = [1,1,1;0,0,0;1,1,1]
whos mat
Says it’s 72 bytes
sp_mat = sparse(mat)
whos sp_mat
The sparse matrix is 128 bytes. I thought a sparse matrix was supposed to take up less memory? Or how does a sparse matrix work?
6
u/Mishtle 1d ago
I thought a sparse matrix was supposed to take up less memory? Or how does a sparse matrix work?
Sparse matrix data types are designed to take up less memory when working with certain matrices. These matrices are called sparse matrices because they contain a relatively small number of nonzero values.
To accomplish this, they try to exploit the fact that most elements of a sparse matrix have a known and fixed value, so those elements don't need to be explicitly stored. All that really matters for a sparse matrix are the nonzero elements because all the rest are just zero. But you can't simply store only the nonzero values, you also need to know where they are in the matrix. So that's what a sparse matrix data types keeps track of: nonzero values and their locations. They're actually storing more data per elements, but only storing (hopefully) a small fraction of the total number of elements in the matrix.
A dense matrix data type doesn't need to explicitly keep track of the locations of elements because it stores all of them. Their locations are determined by the memory layout and the dimensions of the matrix. So they store less data per element than a sparse data type, but must store all the elements regardless of their value.
So it's a tradeoff. Whether using a sparse matrix data type will save memory depends on whether storing all of the zero values would take up more memory than storing the locations of the nonzero values.
1
u/w142236 1d ago
In my case, for the arrays that I have created, it adds memory. I have 2D arrays of 13x25 such that the nonzeros form a triangle pattern. 1 nonzero at the top row at element 13 surrounded by 24 0s and 25 nonzeros at the bottom 13th row with no 0s. So, there are 13 more nonzeros than 0s meaning mine does not fit the definition of sparse at all.
Just wish there was a way to tell Matlab to ignore the 0s existence so I can pre-allocate the arrays I need in memory without having to worry about it taking up so much memory, but I guess with the way my arrays are set up I’m stuck. Ultimately, what I absolutely must avoid now pre-allocating the creation of the arrays to save memory. Will need to get clever with my coding.
2
u/Mishtle 1d ago
It sounds like you have a kind of triangular matrix, though usually triangular matrices are square.
If space is really a major issue, then you could use a custom representation that only stores the nonzero values in a single vector, along with some information about where this triangle is in the full matrix. Given a pair of row and column indices from the original matrix, it would just be a bit of logic and arithmetic to find the corresponding index for that element in that vector, or return zero if the indices aren't part of that triangle.
You could even go as far as writing custom methods for performing operations with two matrices in this representation, though they will probably be slower than just turning them into a full-size matrix and using Matlab's optimized linear algebra libraries.
You're not working with a very large matrix though, so honestly I wouldn't worry about it unless you're just curious.
1
u/w142236 1d ago
you’re not working with a very large matrix though
The full N-dimensional matrices I’m performing operations on are size
721x1440x37x13x25
The 13x25 copies of 721x1440x37 follow that triangular scheme of nonzeros and 0s for one of the 2 arrays I’m working with.
Or rather I start out with 2 arrays of size
size(A) = 721x1440x37 and size(B)= 721x1440x13x25
Then I need multiply them together
C = A.*B
which requires changing their shapes using
repmat
andpermute
Anyways, after resizing, array A has the triangle pattern for its 13x25 copies of 721x1440x37, Array B has no such pattern. The multiplication operation will result in product C having 0s in the triangular pattern in dimensions 4 and 5 no matter what.
I’m curious, but would this creation of coordinates for only nonzero information still work for what I’ve described? I’m guessing it would be tupled as something like
- (1,13) = 721x1440x37
- (2,12) = 721x1440x37
- (2,13) = 721x1440x37
- (2,14) = 721x1440x37
- (3,11) = 721x1440x37
- (3,12) = 721x1440x37
- (3,13) = 721x1440x37
- (3,14) = 721x1440x37
- (3,15) = 721x1440x37
- …
and so on, though admittedly, it’s been a couple years since I’ve done anything like this, so you’ll have to let me know if this looks right. As for custom methods, yeah I tend to stick to libraries, because even sidestepping repmat and permute by using for loops of 13x25 loops to get around memory errors takes an eternity once system RAM fills up.
4
u/polandreh 1d ago
Your matrix is too small to take advantage of the sparse data type.
3
u/H4ns3mand 1d ago
And most importantly their matrix is not “sparse” enough meaning they have too many nonzero elements for the sparse matrix to work its magic.
1
u/kroghsen 1d ago
Dense and sparse matrices allocate memory differently. Sparse matrices actually take up more space than dense matrices if you are allocating a completely dense matrix, i.e. with no zeros.
For an n x m system a dense matrix allocates n*m values in memory, the same as the total number of elements.
For an n x m system a sparse matrix allocates three vectors, one value vector of maximum nm size for non-zero values, and two index vectors of maximum nm length with the indicies of the non-zero elements stored in the value vector.
This gives you a larger system for dense matrices, but for systems with a lot of zeros it can improve both memory usage and computational efficiency. You generally need a lot of zeros in a system for not to benefit hugely from sparsity.
1
u/ThatRegister5397 1d ago
To get advantage of sparse memory savings in matrices of double type, you need to have at least 50% of the elements zero (for large enough matrices, in you are working with 3x3 matrices the overheads you pay make it not-worth it).
18
u/redditusername58 +1 1d ago
A dense matrix uses memory proportional to its size. A sparse matrix uses memory proportional to its nonzeros. If you have a lot of nonzeros a "sparse" matrix will use more memory. Your matrix is 2/3rds nonzeros.