Solving a large system takes too much memory?

Question

Suppose i have a sparse matrix M with the following properties:

size(M) -> 100000 100000
sprank(M) -> 99236
nnz(M) -> 499987
numel(M) -> 1.0000e+10

How come solving the system takes way more than 8GB of RAM? whos('M') gives only 8.4mb.

I'm using the following code (provided at http://www.mathworks.com/moler/exm/chapters/pagerank.pdf)

function x = pagerank(G,p)

G = G - diag(diag(G));

[n,n] = size(G);
c = full(sum(G,1));
r = full(sum(G,2)); 

% Scale column sums to be 1 (or 0 where there are no out links).

k = find(c~=0);
D = sparse(k,k,1./c(k),n,n);

% Solve (I - p*G*D)*x = e

e = ones(n,1);
I = speye(n,n);
x = (I - p*G*D)\e;

% Normalize so that sum(x) == 1.

x = x/sum(x);`

I must say that I use a 32Gb of RAM memory in order to be able to use mldivide (\) without problems for matrices your size. — Ander Biguri, Nov 03 '14 at 10:17

Ander Biguri · Accepted Answer · 2014-11-03T10:28:35.503

Left divide! that x = (I - p*G*D)\e does way more things that what it seems!

From Matlab mldivide for sparse matrices:

enter image description here

Not all the solvers take the same amount of memory, and some of them take a lot. Left dividing in Matlab is fantastic, but you need to know what you are doing.

I suggest to have a look to some iterative solvers if you run out of memory, such as Preconditioned Conjugate Gradient (PGC) or Algebraic Multigrid (AMG) or in case of complex numbers I think Biconjugate gradients stabilized method works fine

If you dont know where to start, I highly recommend PGC. In the project I am working on my code for left dividing is something like:

% CAUTION! PSEUDOCODE! do not try to run
try
   x=A\b
catch
   x=pgc(A,b) 
end

Solving a large system takes too much memory?

1 Answers1