Out of memory - an alternative to this algorithm?

3 views (last 30 days)
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);
  1 Comment
KSSV
KSSV on 12 Jul 2017
combinations is not given......a function is also not given..

Sign in to comment.

Accepted Answer

Walter Roberson
Walter Roberson on 12 Jul 2017
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.
  6 Comments
Ulrik William Nash
Ulrik William Nash on 27 Jul 2017
Thank you Walter, yes, I did.
Unfortunately, after implementing your solution of "chopping and compressing" more frequently than I had done, the memory consumption of MATLAB is surprisingly out of tune with the size of the matrices being generated. This I cannot understand (see attached image, which shows the memory usage climbing from the start of the script till it drops at the finish).
Do you have any idea what might be going on? And any idea about solutions? I have thought about crunching segments of states, saving the output, moving to the next segment of states, and so on, with clearvars in between. Is that wise?
Walter Roberson
Walter Roberson on 27 Jul 2017
Be cautious: clearing variables in a loop is expensive. I suspect is less expensive to assign empty array to them, but that would need to be timed.

Sign in to comment.

More Answers (1)

Jan
Jan on 12 Jul 2017
Edited: Jan on 12 Jul 2017
This note seems to be important:
combinations the number of combinations in E_perms, a matrix holding
(1/L + 1)^n possible states. This can obviously be extremenly large.
For the given data, n = 5, L = 0.1, you get 161'051. Is this "extremely large" already? How large is E_perms and u? What is k? Is transitionProbability a user defined function?

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!