I have a large simple graph G, which has about 100k node, and its adjacency matrix A (sparse, symmetric and binary). I need to calculate (A*A).A, but unfortunately A*A causes memory error in MATLAB. Is there any efficient way to do that?
Note: I tried with sparse matrix format.
First off: I'm assuming nnz(A) is fairly low. I just tested this with nnz(A) = 9999963, and size(A) = 1000000x1000000. The intuitive approach is to work with the data in "chunks". Take the first 10000 columns (all rows) and the first 10000 rows (all columns), the next 10000, the next etc. I believe this should avoid the memory problems.
I've just tested A*A, and got the same memory problems as you did. What I did was, convert A to logical: A_logical = logical(A). This reduces the size of your matrix quite a bit. Note, you can't use uint8 or something similar, since the only datatypes supported by sparse are logical and double.
Now, A_logical*A_logical fails with the error message:
Error using * Both logical inputs must be scalar.
However, squaring a logical matrix works fine:
A_square = A_logical^2;
Note, the result of the A_logical^2 is not a logical matrix, but a double, so you will get the correct values, not only 1 and 0.
This worked fine for me with no memory problems. The computer halted for about 20 seconds, so it's a "tough" computation, but it worked.