Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
dense to ell sparse format

Subject: dense to ell sparse format

From: Piero Lanucara

Date: 23 Mar, 2011 11:10:04

Message: 1 of 6

Dear sirs
I used a simple intuitive script to generate an itpack (ell) sparse format
The simple script is:
[i,j,temp]=find(A);
for k=1:size(A,1)
ii=i(i==k);
jj=j(ii);
tt=temp(ii);
B(k,1:size(tt,1))=tt;
I(k,1:size(tt,1))=jj;
end

it works and is sufficiently fast for little sparse matrices but, of course, is very slow with huge matrices (nnz 1 million or more). Some useful suggestions?

Lpeter

Subject: dense to ell sparse format

From: Bruno Luong

Date: 23 Mar, 2011 13:27:04

Message: 2 of 6

"Piero Lanucara" <lanucara@caspur.it> wrote in message <imckec$nlc$1@fred.mathworks.com>...
> Dear sirs
> I used a simple intuitive script to generate an itpack (ell) sparse format
> The simple script is:
> [i,j,temp]=find(A);
> for k=1:size(A,1)
> ii=i(i==k);
> jj=j(ii);
> tt=temp(ii);
> B(k,1:size(tt,1))=tt;
> I(k,1:size(tt,1))=jj;
> end
>
> it works and is sufficiently fast for little sparse matrices but, of course, is very slow with huge matrices (nnz 1 million or more). Some useful suggestions?
>
> Lpeter

Your code doesn't look right. I guess ii setting should be

ii = i==k;

Bruno

Subject: dense to ell sparse format

From: Bruno Luong

Date: 23 Mar, 2011 13:37:05

Message: 3 of 6

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
> Your code doesn't look right. I guess ii setting should be
>
> ii = i==k;
>

Assuming the code is with correction:

% Data
A=rand(5,6);
A(A<0.5)=0;

% Your engine
clear B I
[i,j,temp]=find(A);
for k=1:size(A,1)
    ii=i==k;
    jj=j(ii);
    tt=temp(ii);
    B(k,1:size(tt,1))=tt;
    I(k,1:size(tt,1))=jj;
end
B
I

% My engine
[j,i,temp]=find(A.'); % Better work with A.' so that "i" is sorted
ii = accumarray(i, 1, [], @(x) {1:size(x)});
ii = [ii{:}].';
B = accumarray([i,ii],temp)
I = accumarray([i,ii],j)

% Bruno

Subject: dense to ell sparse format

From: Piero Lanucara

Date: 23 Mar, 2011 14:28:05

Message: 4 of 6

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <imct21$kua$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
> > Your code doesn't look right. I guess ii setting should be
> >
> > ii = i==k;
> >
>
> Assuming the code is with correction:
>
> % Data
> A=rand(5,6);
> A(A<0.5)=0;
>
> % Your engine
> clear B I
> [i,j,temp]=find(A);
> for k=1:size(A,1)
> ii=i==k;
> jj=j(ii);
> tt=temp(ii);
> B(k,1:size(tt,1))=tt;
> I(k,1:size(tt,1))=jj;
> end
> B
> I
>
> % My engine
> [j,i,temp]=find(A.'); % Better work with A.' so that "i" is sorted
> ii = accumarray(i, 1, [], @(x) {1:size(x)});
> ii = [ii{:}].';
> B = accumarray([i,ii],temp)
> I = accumarray([i,ii],j)
>
> % Bruno



that's great!
it works fine wih huge symmetric matrix with something like 120Million of non zeros
the interesting thing is that the ell matrix in output is very compact (1 Million x 471 elements!) end this has nice property for solvers.....
Lpeter
p.s
I think my original release should work..the only difference is that

ii=i(i==k) %it generate a small vector with respect the original size
ii=i==k %it generate a vector of the same dimension of i

Subject: dense to ell sparse format

From: Bruno Luong

Date: 23 Mar, 2011 14:40:05

Message: 5 of 6

"Piero Lanucara" <lanucara@caspur.it> wrote in message <imd01k$hvf$1@fred.mathworks.com>...

> p.s
> I think my original release should work..the only difference is that
>
> ii=i(i==k) %it generate a small vector with respect the original size
> ii=i==k %it generate a vector of the same dimension of i

I disagree. ii=i(i==k) returns an array of repeated number of k, and later spoils jj and tt.

Bruno

Subject: dense to ell sparse format

From: Piero Lanucara

Date: 23 Mar, 2011 14:53:05

Message: 6 of 6

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <imd0o5$199$1@fred.mathworks.com>...
> "Piero Lanucara" <lanucara@caspur.it> wrote in message <imd01k$hvf$1@fred.mathworks.com>...
>
> > p.s
> > I think my original release should work..the only difference is that
> >
> > ii=i(i==k) %it generate a small vector with respect the original size
> > ii=i==k %it generate a vector of the same dimension of i
>
> I disagree. ii=i(i==k) returns an array of repeated number of k, and later spoils jj and tt.
>
> Bruno

I'm sorry I ckeck and you have right absolutely !

thanks
LPeter

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us