MATLAB: Out of memory – an alternative to this algorithm

markov chainmemory conservationsparsetransition matrix

I am working on Markov Chain problem involving a large, sparse transition matrix. Unfortunately, in generating the transition matrix as I do, my system quickly runs out of memory. Is my algorithm (seen below) causing this problem unnecessarily early, or is it just the nature of the problem that prevents computation on my system?
n = 5;
L = 0.1;
r = [];
c = [];
s = [];
for i = 1:combinations % combinations the number of combinations in E_perms, a matrix holding (1/L + 1)^n possible states. This can obviously be extremenly large.
     state_0 = u(i,:);
    [states_1,transition_probs] = transitionProbability(state_0,k,L,E_perms); % A function that generates a vector of possible states after state_0, and the associated probabilites of transitioning to them. Note that only a small subset of all states can be reached from state_0 so the final transition matrix is very sparse. 
    for ii = 1:size(states_1(:,1))
        [~,indx] = ismembertol(states_1(ii,:),u,0.00001,'ByRows', true);
        r = [r i];
        c = [c indx];
        s = [s transition_probs(ii,1)];
    end
end
transition_matrix = accumarray([r',c'],s',[],[],[],1);

Best Answer

Your indx values could be up to numel(u) and your ii values can be up to combinations. That should give you enough information to be able to spalloc() a result matrix before doing any looping.
Now, as you go through, do not build a overall r, c, s matrices: build them per i. Then after the ii loop, accumarray what you got from that loop, and specify the known maximum sizes as your third parameter for accumarray . Continue to specify sparse for that matrix. After you have built that matrix with the same sparse bounds as the transition_matrix , add it to the transition_matrix .
Your working memory would then be only enough for one generation, in linear form, plus the sparse memory for representing that linear in sparse form, plus the memory for the sparse final matrix. I guess potentially you could need up to twice the memory of the sparse final matrix as it is probably not going to do the sparse addition "in place".
Your current system requires three arrays full of linear information, plus enough memory to store the sparse final array, so by my calculation building iteratively should require less memory.
Related Question