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:
Indexing into large sparse matrix

Subject: Indexing into large sparse matrix

From: NIcholas

Date: 24 Mar, 2009 20:44:02

Message: 1 of 9

I have a large sparse matrix with number of elements exceeding the maximum variable size allowed in matlab (though number of rows and columns do not) e.g. A = sparse([],[],[],10e6,10e6,0))

I have a list of row indices r, and colomn indices c (numel(r)==numel(c)). I would like to extract the elements A(r(i),c(i)) for i=1:numel(r). For a small matrix I could index as A(sub2ind(size(A),r,c)), however for large A I get the error that it can't index into A since "maximum variable size allowed by the program is exceeded". I was wondering if there was a way to extract these values without looping over the r, c index.

Thanks,
Nick

Subject: Indexing into large sparse matrix

From: Matt

Date: 24 Mar, 2009 21:50:18

Message: 2 of 9

"NIcholas" <remove.this_nmg33@cornell.edu> wrote in message <gqbgmi$ll6$1@fred.mathworks.com>...
> I have a large sparse matrix with number of elements exceeding the maximum variable size allowed in matlab (though number of rows and columns do not) e.g. A = sparse([],[],[],10e6,10e6,0))
>
> I have a list of row indices r, and colomn indices c (numel(r)==numel(c)). I would like to extract the elements A(r(i),c(i)) for i=1:numel(r). For a small matrix I could index as A(sub2ind(size(A),r,c)), however for large A I get the error that it can't index into A since "maximum variable size allowed by the program is exceeded". I was wondering if there was a way to extract these values without looping over the r, c index.

In general, probably not, but there may be workarounds if you tell us how r,c were generated.

In particular, do you have to index into A? Or could you perhaps index into nonzeros(A) ?

Subject: Indexing into large sparse matrix

From: Bruno Luong

Date: 24 Mar, 2009 22:10:05

Message: 3 of 9

"NIcholas" <remove.this_nmg33@cornell.edu> wrote in message <gqbgmi$ll6$1@fred.mathworks.com>...
> I have a large sparse matrix with number of elements exceeding the maximum variable size allowed in matlab (though number of rows and columns do not) e.g. A = sparse([],[],[],10e6,10e6,0))
>
> I have a list of row indices r, and colomn indices c (numel(r)==numel(c)). I would like to extract the elements A(r(i),c(i)) for i=1:numel(r). For a small matrix I could index as A(sub2ind(size(A),r,c)), however for large A I get the error that it can't index into A since "maximum variable size allowed by the program is exceeded". I was wondering if there was a way to extract these values without looping over the r, c index.
>
> Thanks,
> Nick

function v = spsubidx(S, r, c)
if any(r(:)<1) || any(r(:)>size(S,1))
    error('Row subscript out of range')
end
if any(c(:)<1) || any(c(:)>size(S,2))
    error('Row subscript out of range')
end
[I J s]=find(S);
[tf loc]= ismember([r(:) c(:)],[I J],'rows');
v = zeros(size(tf));
v(tf) = s(loc(tf));
end % spsubidx

% Command line
A=sparse(10e6,10e6,pi,10e6,10e6)
spsubidx(A,[1 1 size(A,1)],[1 1 size(A,2)])

% Bruno

Subject: Indexing into large sparse matrix

From: Bruno Luong

Date: 24 Mar, 2009 22:17:01

Message: 4 of 9

Sorry, the second error message should be:
error('Column subscript out of range')

Bruno

Subject: Indexing into large sparse matrix

From: NIcholas

Date: 24 Mar, 2009 22:32:01

Message: 5 of 9

The application is a "sparse image" filtering. I have a large set of grid points with weights (intensities) and I am trying to filter this image with a gaussian and I am only interested in the value at non-zero locations in the original image - this arose as a discretization of a Kernel Density Estimation where I am only interested in the value of the PDF at the sample points - I was trying to make this quicker than O(N^2) and using a discrete grid makes it O(N*K) where K is the number of non-zero elements in the (truncated) Gaussian kernel.

I planned to implement this as:
[rr,cc,zz] = find(A);
g = fspecial('gaussian', sz, sig);
PDF=0;
for i=1:size(g,1)
for j=1:size(g,2)
rNew = r - (sz(1)/2-1+i);
cNew = c - (sz(2)/2-1+j);
ind = sub2ind(size(A), rNew , cNew);
PDF = PDF + g(i)*A(ind);
end
end

I wrote a simple mex function to extract the rNew,cNew elements from A (using the rr,cc index from find(A)).

I also tried A(sparse(rNew,cNew,true,size(A,1),size(B,2))) - which is essentially what my mex function is computing - but I got a similar error: "Indices are too large to convert to linear index".


"NIcholas" <remove.this_nmg33@cornell.edu> wrote in message <gqbgmi$ll6$1@fred.mathworks.com>...
> I have a large sparse matrix with number of elements exceeding the maximum variable size allowed in matlab (though number of rows and columns do not) e.g. A = sparse([],[],[],10e6,10e6,0))
>
> I have a list of row indices r, and colomn indices c (numel(r)==numel(c)). I would like to extract the elements A(r(i),c(i)) for i=1:numel(r). For a small matrix I could index as A(sub2ind(size(A),r,c)), however for large A I get the error that it can't index into A since "maximum variable size allowed by the program is exceeded". I was wondering if there was a way to extract these values without looping over the r, c index.
>
> Thanks,
> Nick

Subject: Indexing into large sparse matrix

From: Matt

Date: 24 Mar, 2009 22:46:01

Message: 6 of 9

"NIcholas" <remove.this_nmg33@cornell.edu> wrote in message <gqbn11$9c2$1@fred.mathworks.com>...
> The application is a "sparse image" filtering. I have a large set of grid points with weights (intensities) and I am trying to filter this image with a gaussian and I am only interested in the value at non-zero locations in the original image -
---------------------------

If A represents the original image, then all this would require is

>>PDF(A~=0)

Subject: Indexing into large sparse matrix

From: Matt

Date: 24 Mar, 2009 22:48:02

Message: 7 of 9

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gqblnt$7c7$1@fred.mathworks.com>...
>
> function v = spsubidx(S, r, c)
> if any(r(:)<1) || any(r(:)>size(S,1))
> error('Row subscript out of range')
> end
> if any(c(:)<1) || any(c(:)>size(S,2))
> error('Row subscript out of range')
> end
> [I J s]=find(S);
> [tf loc]= ismember([r(:) c(:)],[I J],'rows');
> v = zeros(size(tf));
> v(tf) = s(loc(tf));
> end % spsubidx
>
> % Command line
> A=sparse(10e6,10e6,pi,10e6,10e6)
> spsubidx(A,[1 1 size(A,1)],[1 1 size(A,2)])
>
> % Bruno

Just as a side note, the above approach works only provided that you are trying to index exclusively into nonzero elements of S. That does happen to be what the OP wants, but we only found that out afterward...

Subject: Indexing into large sparse matrix

From: Bruno Luong

Date: 24 Mar, 2009 22:55:18

Message: 8 of 9

"Matt " <xys@whatever.com> wrote in message <gqbnv1$b9q$1@fred.mathworks.com>...

>
> Just as a side note, the above approach works only provided that you are trying to index exclusively into nonzero elements of S.

No, it works for all cases, including indexing to zero.

Bruno

Subject: Indexing into large sparse matrix

From: Matt

Date: 24 Mar, 2009 23:04:01

Message: 9 of 9

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gqbocm$a1e$1@fred.mathworks.com>...
> "Matt " <xys@whatever.com> wrote in message <gqbnv1$b9q$1@fred.mathworks.com>...
>
> >
> > Just as a side note, the above approach works only provided that you are trying to index exclusively into nonzero elements of S.
>
> No, it works for all cases, including indexing to zero.
>
> Bruno

Alright, I see it now

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