Problems with memory allocation - large-dimensional matrices

I have the following piece of code, where Deg_Assign_List is a matrix (only with 1’s or 3’s) with 20 columns and the number of rows depends on the case I'm considering, which is based on the value of m, that can be any integer from 2 to 20. Everything works fine for small values of m. For the case m = 15 the program is running, but it's too slow, I couldn't get any results. For larger values of m it gives errors like below. I've already checked answers of questions related to this memory problem, which involves large storage, and I've tried changing a few things, such as using the sparse function instead of zeros at initialization or using the function clear to release matrix M_aux from system memory when no longer needed. The problem is that I can't see how to store the information of M_aux and Edge_Assign_List matrices efficiently and without causing memory allocation errors. Is there any way to change this part of the code so that I can run it for all values of m in matlab?

Indices = [21,22,23;21,23,24;21,24,25;21,25,26;21,26,22;22,27,23;23,27,28;23,28,24;24,28,29;...
    24,29,25;25,29,30;25,30,26;26,30,31;26,31,22;27,22,31;27,31,32;27,32,28;28,32,29;...
    29,32,30;30,32,31];
...
    
for i = 1:size(Deg_Assign_List,1)
    
    ...
        
    n = 1;
    Edge_Assign_List = sparse(3^m,20);
    
    for j = 1:20
        if Deg_Assign_List(i,j) == 1   % assignment of degree 1
            M_aux = repelem(Indices(j,:)', 3^(m-1), 1);
            Edge_Assign_List(:,n) = repmat(M_aux,3^m/numel(M_aux),1);
            m = m - 1;   
            save_T(n) = j;
            n = n + 1;
        else                           % assignment of degree 3
            M_aux = Indices(j,:);
            Edge_Assign_List(:,n:n+2) = repmat(M_aux,3^m,1);
            save_T(n:n+2) = j; 
            n = n + 3;
        end
    end  
    clear M_aux
    
    ...
        
end

Requested 1162261467x8 (8.7GB) array exceeds maximum array size preference (8.0GB). This might cause MATLAB to become
unresponsive.

Error in program_assignment (line 95)
            Edge_Assign_List(:,n:n+2) = repmat(M_aux,3^m,1);

Related documentation

Error using repelem
Requested 3486784401x1 (26.0GB) array exceeds maximum array size preference (5.0GB). This might cause MATLAB to become unresponsive.

Error in program_assignment (line 89)
M_aux = repelem(Indices(j,:)', 3^(m-1), 1);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

[Steven Lord]

Can you describe in words not code what the purpose of the program you're writing is? There may be a more efficient way to achieve your goal than creating a very large (many GB) matrix.

From the description I suspect you're trying to create a graph (directed or undirected) object. If so, does this do something close to what you want?

Indices = [21,22,23;21,23,24;21,24,25;21,25,26;21,26,22;22,27,23;23,27,28;23,28,24;24,28,29;...
    24,29,25;25,29,30;25,30,26;26,30,31;26,31,22;27,22,31;27,31,32;27,32,28;28,32,29;...
    29,32,30;30,32,31];
edges = [Indices(:, [1 2]); Indices(:, [1 3]); Indices(:, [2 3])];
D = digraph(edges(:, 1), edges(:, 2));
plot(D)

G = graph(edges(:, 1), edges(:, 2));
figure
plot(G)

figure
plot(simplify(G)) % Replace pairs of edges between the same nodes with 1 edge

[Catarina Pina]

In fact, we can relate the problem to graphs. I have 20 vertices of the dodecahedron and 12 vertices of the icosahedron. Each row i of the Indices vector (with 3 fields), which is associated with vertex i of the dodecahedron, contains the vertices of the icosahedron that can be connected to i. In fact, when the vertices are all connected in the possible ways, we have a disdyakis triacontahedron. The constraints are: - in each vertex of the dodecahedron, I can only have 1 or 3 connections to vertices of the icosahedron; - all the vertices must have even valence. What I'm doing in the program is obtaining all the possible representations, up to isomorphism (by actions of the 120-element icosahedral symmetry group). First I create the Edge_Assign_List matrix, which contains all the possibilities, and then I check the even degree requirement and remove isomorphic representations. The program is working for small values of m (when there aren't many vertices of the dodecahedron connected to just one of the vertices of the icosahedron), but when m increases I have the memory problem I mentioned. I've only posted the part of the code relating to the error, but I hope I've now explained the problem better.

[Torsten]

And what is the final aim ?

[John D'Errico]

You are running up against the curse of large numbers. Is your computer infinitely large? Infinitely fast? It never is, but we often forget that fact.

A scheme that often works on many small problems is to do as you seem to be doing, generate all possible cases for some process, then throw your computer at it, hoping it can do the work. Great, when m is small. But for larger values of m, you are now tripping over that curse. And, so we see messages like this:

Requested 1162261467x8 (8.7GB) array exceeds maximum array size preference (8.0GB). This might cause MATLAB to become unresponsive.

and

Error using repelem

Requested 3486784401x1 (26.0GB) array exceeds maximum array size preference (5.0GB). This might cause MATLAB to become unresponsive.

26 gigabyte arrays are nasty things to work with, and your computer surely has limited and finite memory. Of course, you can get a bigger computer, with more memory yet. But that will just encourage you to try to solve still bigger problems tomorrow.

It is signal that you need to find a better way to solve a problem, something that has been the task of mathematicians for many years, to find smarter methods when brute force fails. It might mean you need to use other tools. It might mean you need to accept that at best, you can only solve the problem in some sub-optimal sense, using an ad hoc scheme that will only succeed to a limited extent.

[Matt J]

You are attempting to construct a 3^20 x 20 matrix, which doesn't appear to have any zeros at all. Even if you managed to get your code to run successfully, the result will consume 520 GB as a full double matrix,

3^20*20*8/2^30

ans = 519.5714

and three times this much if you store it in sparse-type. Do you have that much RAM? Are you happy to consume that much RAM?

I suppose, seeing as how your example has values less than 255, you could put the result in a uint8 matrix for a total of 65 GB, but I wonder if you even intended for your final result to have such a big footprint..

[Steven Lord]

What I'm doing in the program is obtaining all the possible representations, up to isomorphism (by actions of the 120-element icosahedral symmetry group).

This is not feasible on your computer system. There are too many possible representations to store at once, and even if you could processing them is going to take a while. Let's say you could process a thousand rows a second. [If they're that complicated, I suspect it would take longer, but for sake of argument let's try this thought experiment.] How long would it take to process each row?

numRows = 3^20

numRows = 3.4868e+09

H = hours(seconds(numRows/1e3))

H = 968.5512

D = H/24

D = 40.3563

About 40 days.

If you tell us what you're hoping to do with the final result, we may be able to offer suggestions for a more efficient (in terms of memory and perhaps of time) way to achieve that end goal.

[Stephen23]

Using a SPARSE matrix is likely very counter-productive if the matrix is not actually sparse (sparse = contains mostly zeros). Others have given some good approaches to consider. Another approach might be to slightly munge your data: you wrote that the data contains "only with 1’s or 3’s" : if most of your data are e.g. 1's then you could map 1->0 and still use a SPARSE matrix (with a tiny bit of adjustment of your data going in/out of the matrix).

However, most likely you need to consider another approach to solving this problem: there are many tasks which scale exponentially with the size of the dataset, very easily leading to (predicted) calculation times exceeding the age of the universe.