Thread Subject: Sum Matrix Subset

I have a sparse matrix which can get VERY large which I need to sum row subsets of, and I need it done with no for loops. As an example:

Create a new matrix which is defined by the sum of a finite number of column elements in input matrix

[1 2 3;
 4 5 6; -----would become -------> [5 7 9;
 7 8 9; 17 19 21]
10 11 12]

In this case I am just summing the columns of the two rows, and making that my first row, and then summing the bottom two rows and making that my second row. Its a simple example, however in practice this is dealing with such massive sparse matrices that solutions even involving the full() command will run my 12G of ram out in a fraction of a second. I have tried reshaping this into a N dimensional matrix where each subset is put into a third dimension, (which could work fine) except that there is no way to make a sparse matrix N dimensional, it must be 2 dimensional, and as I said it will crash the computer to remove the sparsity.

I know that I said it before, but I will say it again: I cannot use for loops. So many values last time I tried it changed my execution time from .56 seconds to 350 seconds.

Any help anyone can provide here would be greatly appreciated!

"Daniel Blackmer" <daniel.blackmer@remove.thisgmail.dotcom> wrote in message <hkslll$5h9$1@fred.mathworks.com>...
> I have a sparse matrix which can get VERY large which I need to sum row subsets of, and I need it done with no for loops. As an example:
>
> Create a new matrix which is defined by the sum of a finite number of column elements in input matrix
>
> [1 2 3;
> 4 5 6; -----would become -------> [5 7 9;
> 7 8 9; 17 19 21]
> 10 11 12]
>
> In this case I am just summing the columns of the two rows, and making that my first row, and then summing the bottom two rows and making that my second row. Its a simple example, however in practice this is dealing with such massive sparse matrices that solutions even involving the full() command will run my 12G of ram out in a fraction of a second. I have tried reshaping this into a N dimensional matrix where each subset is put into a third dimension, (which could work fine) except that there is no way to make a sparse matrix N dimensional, it must be 2 dimensional, and as I said it will crash the computer to remove the sparsity.
>
> I know that I said it before, but I will say it again: I cannot use for loops. So many values last time I tried it changed my execution time from .56 seconds to 350 seconds.
>
> Any help anyone can provide here would be greatly appreciated!

Darnit. When posted it messed up my example. Just to clarify:
Input = [1 2 3; 4 5 6; 7 8 9; 10 11 12];
Output = [5 7 9; 17 19 21];

"Daniel Blackmer" <daniel.blackmer@remove.thisgmail.dotcom> wrote in message <hksmc4$jv2$1@fred.mathworks.com>...
> "Daniel Blackmer" <daniel.blackmer@remove.thisgmail.dotcom> wrote in message <hkslll$5h9$1@fred.mathworks.com>...
> > I have a sparse matrix which can get VERY large which I need to sum row subsets of, and I need it done with no for loops. As an example:
> >
> > Create a new matrix which is defined by the sum of a finite number of column elements in input matrix
> >
> > [1 2 3;
> > 4 5 6; -----would become -------> [5 7 9;
> > 7 8 9; 17 19 21]
> > 10 11 12]
> >
> > In this case I am just summing the columns of the two rows, and making that my first row, and then summing the bottom two rows and making that my second row. Its a simple example, however in practice this is dealing with such massive sparse matrices that solutions even involving the full() command will run my 12G of ram out in a fraction of a second. I have tried reshaping this into a N dimensional matrix where each subset is put into a third dimension, (which could work fine) except that there is no way to make a sparse matrix N dimensional, it must be 2 dimensional, and as I said it will crash the computer to remove the sparsity.
> >
> > I know that I said it before, but I will say it again: I cannot use for loops. So many values last time I tried it changed my execution time from .56 seconds to 350 seconds.
> >
> > Any help anyone can provide here would be greatly appreciated!
>
> Darnit. When posted it messed up my example. Just to clarify:
> Input = [1 2 3; 4 5 6; 7 8 9; 10 11 12];
> Output = [5 7 9; 17 19 21];

For your specific example:
a = reshape(Input,2,[]);
b = sum(a);
Output = reshape(b,2,[]);

"ade77 " <ade100a@gmail.com> wrote in message <hkso67$fpe$1@fred.mathworks.com>...
> "Daniel Blackmer" <daniel.blackmer@remove.thisgmail.dotcom> wrote in message <hksmc4$jv2$1@fred.mathworks.com>...
> > "Daniel Blackmer" <daniel.blackmer@remove.thisgmail.dotcom> wrote in message <hkslll$5h9$1@fred.mathworks.com>...
> > > I have a sparse matrix which can get VERY large which I need to sum row subsets of, and I need it done with no for loops. As an example:
> > >
> > > Create a new matrix which is defined by the sum of a finite number of column elements in input matrix
> > >
> > > [1 2 3;
> > > 4 5 6; -----would become -------> [5 7 9;
> > > 7 8 9; 17 19 21]
> > > 10 11 12]
> > >
> > > In this case I am just summing the columns of the two rows, and making that my first row, and then summing the bottom two rows and making that my second row. Its a simple example, however in practice this is dealing with such massive sparse matrices that solutions even involving the full() command will run my 12G of ram out in a fraction of a second. I have tried reshaping this into a N dimensional matrix where each subset is put into a third dimension, (which could work fine) except that there is no way to make a sparse matrix N dimensional, it must be 2 dimensional, and as I said it will crash the computer to remove the sparsity.
> > >
> > > I know that I said it before, but I will say it again: I cannot use for loops. So many values last time I tried it changed my execution time from .56 seconds to 350 seconds.
> > >
> > > Any help anyone can provide here would be greatly appreciated!
> >
> > Darnit. When posted it messed up my example. Just to clarify:
> > Input = [1 2 3; 4 5 6; 7 8 9; 10 11 12];
> > Output = [5 7 9; 17 19 21];
>
> For your specific example:
> a = reshape(Input,2,[]);
> b = sum(a);
> Output = reshape(b,2,[]);

Elegant and it works perfectly! Thank you, you are a lifesaver!

"ade77 " <ade100a@gmail.com> wrote in message <hkso67$fpe$1@fred.mathworks.com>...

> For your specific example:
> a = reshape(Input,2,[]);
> b = sum(a);
> Output = reshape(b,2,[]);
=================


Unfortunately, reshape() is not reliable for large sparse matrice. In this case we were lucky obviously because the matrix wasn't too big. However, consider the following example,

d=100000;
Input=sprand(d,d,.0001);
a=reshape(Input,2,[]);
b=sum(a);

??? Error using ==> reshape
Product of known dimensions, 2, not divisible into total number of elements, 1410065408.


You would have to do the following way, which is probably also going to be faster, even when the matrix size is small enough for reshape() to work:

>> D=kron(speye(d/2),[1 1]);
>> tic; Output=D*Input;toc
Elapsed time is 0.162270 seconds.
>> tic; Output=D*Input;toc
Elapsed time is 0.172060 seconds.