Thread Subject: Structures making large sparse matrices slow?

Structures making large sparse matrices slow?

Dear list,

I noticed that large sparse matrices have a slow call when they are inside a structure. A small (sparse) matrix does not seem to have a problem:

> A = sprand(100,30, 0.1);
> tic, for j=1:10, size(A); end, toc
Elapsed time is 0.000043 seconds.
> Z.A = A;
> tic, for j=1:10, size(Z.A); end, toc
Elapsed time is 0.000039 seconds.

However, for a large sparse matrix:
> B = sprand(6463130, 252, 0.0524);
> tic, for j=1:10, size(B); end, toc
Elapsed time is 0.000040 seconds.
> Z.B = B;
> tic, for j=1:10, size(Z.B); end, toc
Elapsed time is 6.297543 seconds.

With full matrices there does not seem to be a problem:
> C = zeros(10000,10000);
> tic, for j=1:10, size(C); end, toc
Elapsed time is 0.000027 seconds.
> Z.C = C;
> tic, for j=1:10, size(Z.C); end, toc
Elapsed time is 0.000035 seconds.

The problem persists also when allocating the matrix directly in the structure:
> Z.D = sprand(6463130, 252, 0.0524);
> tic, for j=1:10, size(Z.D); end, toc
Elapsed time is 6.534465 seconds.

But it does not seem to harm normal operation:
> tic, for j=1:10, B(100); end, toc
Elapsed time is 0.000045 seconds.
> tic, for j=1:10, Z.B(100); end, toc
Elapsed time is 0.000046 seconds.


Note that I am using a simple command (size) of which the execution time does not (should not) depend on the size of the matrix.

I am using Matlab2008a on 64 bit Linux.

Sincerely,
Sebastiaan

Forgot to mention: the problem is also there for nnz, nzmax, issparse, etc.

I tried to make a mex file which does the same thing as issparse, however I noticed that even an 'empty' call slows Matlab down:

test.c:
#include "mex.h"
void mexFunction(int nlhs, mxArray* plhs[], int nrhs, const mxArray* prhs[])
{ return; }

> mex test.c
> tic, for j=1:10, test(Z.B); end, toc
Elapsed time is 6.474021 seconds.

While it does not actually do anyting...

"Sebastiaan" <s.breedveld@erasmusmc.REMOVE.BOO.BOO.nl> wrote in message <gp2tlp$s7c$1@fred.mathworks.com>...
> Structures making large sparse matrices slow?
>
> Dear list,
>
> I noticed that large sparse matrices have a slow call when they are inside a structure. A small (sparse) matrix does not seem to have a problem:
>
> > A = sprand(100,30, 0.1);
> > tic, for j=1:10, size(A); end, toc
> Elapsed time is 0.000043 seconds.
> > Z.A = A;
> > tic, for j=1:10, size(Z.A); end, toc
> Elapsed time is 0.000039 seconds.
>
> However, for a large sparse matrix:
> > B = sprand(6463130, 252, 0.0524);
> > tic, for j=1:10, size(B); end, toc
> Elapsed time is 0.000040 seconds.
> > Z.B = B;
> > tic, for j=1:10, size(Z.B); end, toc
> Elapsed time is 6.297543 seconds.
>
> With full matrices there does not seem to be a problem:
> > C = zeros(10000,10000);
> > tic, for j=1:10, size(C); end, toc
> Elapsed time is 0.000027 seconds.
> > Z.C = C;
> > tic, for j=1:10, size(Z.C); end, toc
> Elapsed time is 0.000035 seconds.
>
> The problem persists also when allocating the matrix directly in the structure:
> > Z.D = sprand(6463130, 252, 0.0524);
> > tic, for j=1:10, size(Z.D); end, toc
> Elapsed time is 6.534465 seconds.
>
> But it does not seem to harm normal operation:
> > tic, for j=1:10, B(100); end, toc
> Elapsed time is 0.000045 seconds.
> > tic, for j=1:10, Z.B(100); end, toc
> Elapsed time is 0.000046 seconds.
>
>
> Note that I am using a simple command (size) of which the execution time does not (should not) depend on the size of the matrix.
>
> I am using Matlab2008a on 64 bit Linux.
>
> Sincerely,
> Sebastiaan

Hi Sebastiaan.

The issue here is that MATLAB is not being as lazy as it could be for sparse matrices. So you know, we added the same optimization for sparse matrices as for dense matrices in R2008b. That is, the time for the operation above is independent of matrix size for both sparse and dense matrices in R2008b and beyond.

Pat.

>
> Hi Sebastiaan.
>
> The issue here is that MATLAB is not being as lazy as it could be for sparse matrices. So you know, we added the same optimization for sparse matrices as for dense matrices in R2008b. That is, the time for the operation above is independent of matrix size for both sparse and dense matrices in R2008b and beyond.
>
> Pat.

Dear Pat,

I have installed R2009a and the difference in execution times disappeared.

However, this keeps me puzzled in the way I thought Matlab handles structure arrays. What I understood from the manual is this:
A = sparse(..); % Allocate memory
B.A = A; % make a pointer to A for the first field of structure B

So what I expected is that nnz(B.A) parses the pointer of A to nnz, and there is no reason for any difference in speed. Where am I going wrong?

Thanks!