Out of memory - an alternative to this algorithm?

1 次查看（过去 30 天）
Ulrik William Nash
Ulrik William Nash 2017-7-12
评论： Walter Roberson 2017-7-27
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);

请先登录，再回答此问题。

采纳的回答

Walter Roberson
Walter Roberson 2017-7-12
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 个评论
显示 4更早的评论
Ulrik William Nash
Ulrik William Nash 2017-7-27
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 2017-7-27
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.

请先登录，再进行评论。

更多回答（1 个）

Jan
Jan 2017-7-12
编辑：Jan 2017-7-12
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?

类别

在 Help Center 和 File Exchange 中查找有关 Sparse Matrices 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by