Solving a large system takes too much memory?

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
   who's('M') -> 8.4mb

How come solving the system takes way more than 8GB of RAM?

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);`

Answer 1

[Vidhi Agarwal]

Hi @Michael

The memory issue you're experiencing likely stems from the demands of solving a large sparse linear system in MATLAB. Here's breakdown:

• Matrix Size and Operations: Although your sparse matrix 'M' has 10 billion elements with only 499,987 non-zero elements, certain operations may inadvertently convert parts of the matrix to a dense format, increasing memory usage. Specifically, solving the system (I - p*G*D)\e can be problematic. While (G) and (D) are sparse, the resulting matrix (I - p*G*D) might not remain sparse during factorization.
• LU Factorization: The backslash operator (\backslash) in MATLAB typically involves LU factorization, which can introduce significant fill-in, making the LU factors denser than the original sparse matrix and thus consuming more memory.
• Memory Overhead: Additional memory is needed for temporary variables, the solution vector, and managing sparse matrix operations, contributing to the increased memory demand.

Some recommendations that might help in resolving the issue is:

• For large sparse systems, consider using iterative solvers like “pcg” (Preconditioned Conjugate Gradient) or “gmres” with appropriate preconditioning. These methods generally use less memory than direct solvers like LU factorization.
• Use MATLAB's memory profiling tools to identify where the most memory is being used. This can help pinpoint operations that cause excessive memory usage.
• If possible, adjust the damping factor “p” and the structure of G to see if that impacts memory usage.

For detailed understanding of “pcg” and “gmres”, as well as MATLAB’s memory profiling tool please refer to following documentation:

• https://www.mathworks.com/help/matlab/ref/pcg.html
• https://www.mathworks.com/help/matlab/ref/gmres.html
• https://www.mathworks.com/help/matlab/performance-and-memory.html

Hope that helps!.