Large Matrix multiplication and out of memory error in matlab

i have sparse matrix V of size V =<162000x32400 double> or even bigger , I have to solve the following equations.

             x_0=ones(size(V ,1) ,1);
             y_0=V'*x_0;
             result=V'*V + y_0*y_0';   %%%%%Problem here

The problem is in right hand side of last equation and is giving me out of memory error.

Answer 1

[Titus Edelhofer]

Hi Imran,

here an update taking care of the "not multiple" issue:

n = size(V,2);
blksize = 500;
result = zeros(n);
for i=0:(n/blksize-1)
  columns = i*blksize + (1:blksize);
  result(:, columns) = V'*V(:,columns) + y_0*y_0(columns)';
end

% n not a multiple of blksize?
if columns(end)
  columns = (columns(end)+1):n;
  result(:, columns) = V'*V(:,columns) + y_0*y_0(columns)';
end

Again, you will need to play with the blksize (which now is indeed a blksize not like above a number of blocks) ...

Titus

[imran khan]

Thanks, i will try it and let you know.

Answer 2

[Walter Roberson]

Is y_0=V'*x_0; the same as sum(V) ?

[imran khan]

It is equivalent to sum(V)'

Answer 3

[Jan]

A [162000x32400] DOUBLE array needs 42GB memory. I'm not sure if computing V'*V + y_0*y_0' needs to allocate one, two or three further blocks of this size as temporary memory. In every case the blocks must be available in contiguos blocks. Therefore I estimate you need 128 to 256 GB free RAM.

How many RAM do you have installed?

(Is V sparse?) [EDITED:] How sparse is V?

[Walter Roberson]

The problem statement does start by saying V is sparse.

[imran khan]

I have 8 Gb ram installed.

[imran khan]

The matrix V =<162000x32400 double> is sparse and it contains 6309393 number of nonzero matrix elements , Amount of storage allocated for nonzero matrix elements return by nzmax(V) = 6309393.

Answer 4

[Titus Edelhofer]

Hi Imran,

I guess the problem is, that y_0*y0' most likely will be a full matrix, as long as your V matrix has no columns that sum up to zero. This will fail already as Jan pointed out. You might get along by looping over the columns of your matrix V ...

Titus

[imran khan]

yes, y_0*y_0' is full matrix , that's what creating problem after multiplication it should be of size <32400 x 32400 double >, is there any method of block processing to solve this.

Answer 5

[Titus Edelhofer]

Hi Imran,

something like the following should work:

n = size(V,2);
blksize = 100;
result = zeros(n);
for i=0:(blksize-1)
  columns = i*n/blksize + (1:n/blksize);
  result(:, columns) = V'*V(:,columns) + y_0*y_0(columns)';
end

I must admit I did not check if it is really correct, but should give an impression (and can be verified easily on small example). The blksize can be experimented for balancing memory and speed.

Titus

[imran khan]

Thanks Titus , I have run this code with blksize =100 but i got the following error.

??? Subscript indices must either be real positive integers or logicals.

Error in ==> Testing at 26

result(:, columns) = V'*V(:,columns) + y_0*y_0(columns)';

can you please run it using some dump values.

[Titus Edelhofer]

Hi Imran,

I updated the code (n needs to be the number of columns). by the way, the code assumes, that the number of columns of V is a multiple of the blksize, otherwise one needs to be more careful ...

Titus

[imran khan]

Well i have tried that though i am not getting memory error but two problems first one is the speed is quite slow as it is taking lot of time and secondly what else if V is not multiple of the blksize, because i got values that are not mulitple , how to solve these issues.