Thread Subject:

efficient use of sparse

hai all
A=[5 6 7;5 7 8;3 4 2]
A =
     5 6 7
     5 7 8
     3 4 2
>> B=[3 4 5; 4 6 8;5 6 8]
B =
     3 4 5
     4 6 8
     5 6 8
>> A+B
ans =
     8 10 12
     9 13 16
     8 10 10
>> whos
  Name Size Bytes Class Attributes
  A 3x3 72 double
  B 3x3 72 double
  ans 3x3 72 double

    C=sparse(A)+sparse(B)

C =

   (1,1) 8
   (2,1) 9
   (3,1) 8
   (1,2) 10
   (2,2) 13
   (3,2) 10
   (1,3) 12
   (2,3) 16
   (3,3) 10

>> whos
  Name Size Bytes Class Attributes

  A 3x3 72 double
  B 3x3 72 double
  C 3x3 124 double sparse

why the use of sparse matrix is much greater than usual use of the matrix?
not by using a sparse, the matrix becomes efficient?

On 3/21/2011 5:35 AM, wahyoe Unggul wrote:

> why the use of sparse matrix is much greater than usual use of the matrix?
> not by using a sparse, the matrix becomes efficient?

It must be a bug in Matlab. It looks like sparse implementation
has a big bug in it.

--Nasser

"wahyoe Unggul" <wahyoe_slipnot@yahoo.co.id> wrote in message <im7gm8$280$1@fred.mathworks.com>...
> hai all
> A=[5 6 7;5 7 8;3 4 2]
> A =
> 5 6 7
> 5 7 8
> 3 4 2
> >> B=[3 4 5; 4 6 8;5 6 8]
> B =
> 3 4 5
> 4 6 8
> 5 6 8
> >> A+B
> ans =
> 8 10 12
> 9 13 16
> 8 10 10
> >> whos
> Name Size Bytes Class Attributes
> A 3x3 72 double
> B 3x3 72 double
> ans 3x3 72 double
>
> C=sparse(A)+sparse(B)
>
> C =
>
> (1,1) 8
> (2,1) 9
> (3,1) 8
> (1,2) 10
> (2,2) 13
> (3,2) 10
> (1,3) 12
> (2,3) 16
> (3,3) 10
>
> >> whos
> Name Size Bytes Class Attributes
>
> A 3x3 72 double
> B 3x3 72 double
> C 3x3 124 double sparse
>
> why the use of sparse matrix is much greater than usual use of the matrix?
> not by using a sparse, the matrix becomes efficient?

Sparse is only efficient when the matrix contains a *majority* of zeros. In your case it's not; why bother with sparse?

Check out this thread:

http://www.mathkb.com/Uwe/Forum.aspx/matlab/147951/Sparse-Matrix-Size-gets-reduces-when-we-take-transpose-of-this

I have provided the memory occupied by sparse matrix in one of the post.

I'm not aware of BUG in sparse storage referred by Nasser.

Bruno

On 3/21/2011 5:35 AM, wahyoe Unggul wrote:

>
> why the use of sparse matrix is much greater than usual use of the matrix?
> not by using a sparse, the matrix becomes efficient?

It is very simple. Sparse has some overhead, some book keeping
data structure. sparse is meant for large matrices with lots of zeros.

No point of using sparse, if the matrix does not have lots of zeros.

If the matrix has lots of zeros, then the overhead will more
than worth it because the saving in storage is now more than
the bookkeeping data structure used.

You can see that, when using it dense matrix (no zeros):

>> C_dense=randperm(1000)'*randperm(1000);
>> C_sparse=sparse(C_dense);
  C_dense 1000x1000 8000000 double
  C_sparse 1000x1000 12004004 double sparse

But when using it with a matrix, which is mostly zeros (here
all zero), you'll see the saving:


>> C_dense=zeros(1000);
>> C_sparse=sparse(C_dense);
   C_dense 1000x1000 8000000 double
   C_sparse 1000x1000 4016 double sparse

So, sparse is very efficient, but for matrices for lots of
zeros in them. Which is what it is designed for.

HTH,

--Nasser

On 3/21/2011 5:49 AM, Bruno Luong wrote:

>
> I'm not aware of BUG in sparse storage referred by Nasser.
>

I was just having some fun Bruno.

--Nasser

I understand now
what if in a large matrix is not zero?,
and in addition to the "sparse" if there were any other function, which can save the amount of memory

"wahyoe Unggul" <wahyoe_slipnot@yahoo.co.id> wrote in message <im7j54$hgd$1@fred.mathworks.com>...
> I understand now
> what if in a large matrix is not zero?,
> and in addition to the "sparse" if there were any other function, which can save the amount of memory

How will you save memory if the numbers are
arbitrary and not zero?

Sparse storage gains because the zero elements
are not stored.

John

"wahyoe Unggul" <wahyoe_slipnot@yahoo.co.id> wrote in message <im7j54$hgd$1@fred.mathworks.com>...
> I understand now
> what if in a large matrix is not zero?,
> and in addition to the "sparse" if there were any other function, which can save the amount of memory

Ah no. Miracle does not happen in the computer. You could store in single or other classes if low accuracy is not an issue.

Bruno

"wahyoe Unggul" <wahyoe_slipnot@yahoo.co.id> wrote in message
news:im7gm8$280$1@fred.mathworks.com...
> hai all
> A=[5 6 7;5 7 8;3 4 2]

*snip*

>>> whos
> Name Size Bytes Class Attributes
> A 3x3 72 double B 3x3
> 72 double ans 3x3 72 double
> C=sparse(A)+sparse(B)

*snip*

>>> whos
> Name Size Bytes Class Attributes
>
> A 3x3 72 double B 3x3
> 72 double C 3x3 124 double sparse
> why the use of sparse matrix is much greater than usual use of the matrix?
> not by using a sparse, the matrix becomes efficient?

For a non-sparse matrix of size [m, n] MATLAB has to use enough memory to
store m*n entries.

For a sparse matrix of size [m, n] MATLAB has to use an amount of memory
that depends on m and n (but not m*n) as well as the number of nonzero
elements. For your particular problem ALL the elements of C are nonzero and
that means it has to use memory to store m*n elements PLUS additional memory
dependent on m and n.

Do not use SPARSE to store a matrix that is not sparse, for which
nnz(A)/numel(A) is close to 1. In your particular case that ratio is equal
to 1, and as you can see that requires more memory that storing the matrix
as a dense matrix.

Just so no one misunderstands Nasser's joke, this is NOT a bug.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

On 3/21/2011 6:33 AM, Bruno Luong wrote:

> Ah no. Miracle does not happen in the computer. You could store in single or
> other classes if low accuracy is not an issue.
>
> Bruno

Another method to save memory, which I intent to patent soon, is to
store the matrix on disk.

This way, no memory is used at all. Much more efficient than sparse as well.

--Nasser

I mean, what if there is a large matrix and has no zeros, whether spase matrix can still be efficient?

"wahyoe Unggul" <wahyoe_slipnot@yahoo.co.id> wrote in message <im7kn5$g3k$1@fred.mathworks.com>...
> I mean, what if there is a large matrix and has no zeros, whether spase matrix can still be efficient?

NO, NO, and NO.

Bruno

"wahyoe Unggul" <wahyoe_slipnot@yahoo.co.id> wrote in message <im7kn5$g3k$1@fred.mathworks.com>...
>
> I mean, what if there is a large matrix and has no zeros, whether spase matrix can still be efficient?
================

There is one situation where you might want to do this. If you are going to be multiplying this non-zero matrix by an even larger, but very sparse matrix, you might want both matrices to be sparse type to ensure that the matrix product is returned as type sparse.

For example, in the code below, I am storing A quite inefficiently, but it's worth it because the resulting larger matrix C is much more memory efficient than Cfull, obtained by using A in non-sparse form,

A=sparse( rand(1000) );
 Afull=full(A);
 
B=sprand(30000, 1000,.00001);

C=B*A;

Cfull=B*Afull;


>> Whos

  Name Size Kilobytes Class Attributes
                                                           
  A 1000x1000 11722.6602 double sparse
  Afull 1000x1000 7812.5 double
  B 30000x1000 7.4258 double sparse
  C 30000x1000 3519.5352 double sparse
  Cfull 30000x1000 234375 double

"Matt J" wrote in message <im7pp0$n86$1@fred.mathworks.com>...
> "wahyoe Unggul" <wahyoe_slipnot@yahoo.co.id> wrote in message <im7kn5$g3k$1@fred.mathworks.com>...
> >
> > I mean, what if there is a large matrix and has no zeros, whether spase matrix can still be efficient?
> ================
>
> There is one situation where you might want to do this. If you are going to be multiplying this non-zero matrix by an even larger, but very sparse matrix, you might want both matrices to be sparse type to ensure that the matrix product is returned as type sparse.
>
> For example, in the code below, I am storing A quite inefficiently, but it's worth it because the resulting larger matrix C is much more memory efficient than Cfull, obtained by using A in non-sparse form,
>
> A=sparse( rand(1000) );
> Afull=full(A);
>
> B=sprand(30000, 1000,.00001);
>
> C=B*A;
>
> Cfull=B*Afull;
>
>
> >> Whos
>
> Name Size Kilobytes Class Attributes
>
> A 1000x1000 11722.6602 double sparse
> Afull 1000x1000 7812.5 double
> B 30000x1000 7.4258 double sparse
> C 30000x1000 3519.5352 double sparse
> Cfull 30000x1000 234375 double

thanks Matt ..