Efficient multiplication of very large matrices in MATLAB

Question

I don't have enough memory to simply create a diagonal D-by-D matrix, since D is large. I keep getting an 'out of memory' error.

Instead of performing M x D x D operations in the first multiplication, I do M x D operations, but still my code takes ages to run.

Can anybody find a more effective way to perform the multiplication A'*B*A? Here's what I've attempted so far:

D=20000
M=25

A = floor(rand(D,M)*10);
B = floor(rand(1,D)*10);

for i=1:D
    for j=1:M
        result(i,j) = A(i,j) * B(1,j);
    end
end    

manual = result * A';
auto = A*diag(B)*A';
isequal(manual,auto)

Answer 1

One option that should solve your problem is using sparse matrices. Here's an example:

D = 20000;
M = 25;
A = floor(rand(D,M).*10);    %# A D-by-M matrix
diagB = rand(1,D).*10;       %# Main diagonal of B
B = sparse(1:D,1:D,diagB);   %# A sparse D-by-D diagonal matrix
result = (A.'*B)*A;         %'# An M-by-M result

Another option would be to replicate the D elements along the main diagonal of B to create an M-by-D matrix using the function REPMAT, then use element-wise multiplication with A.':

B = repmat(diagB,M,1);   %# Replicate diagB to create an M-by-D matrix
result = (A.'.*B)*A;    %'# An M-by-M result

And yet another option would be to use the function BSXFUN:

result = bsxfun(@times,A.',diagB)*A;  %'# An M-by-M result

Answer 2

Maybe I'm having a bit of a brainfart here, but can't you turn your DxD matrix into a DxM matrix (with M copies of the vector you're given) and then .* the last two matrices rather than multiply them (and then, of course, normally multiply the first with the found product quantity)?

Answer 3

1. You are getting "out of memory" because MATLAB can not find a chunk of memory large enough to accommodate the entire matrix. There are different techniques to avoid this error described in MATLAB documentation.

2. In MATLAB you obviously do not need programming explicit loops in most cases because you can use operator *. There exists a technique how to speed up matrix multiplication if it is done with explicit loops, here is an example in C#. It has a good idea how (potentially large) matrix can be split into smaller matrices. To contain these smaller matrices in MATLAB you can use cell matrix. It is much more probably that system finds enough RAM to accommodate two smaller sub-matrices then the resulting large matrix.