MATLAB Central Newsreader - Indexing into large sparse matrix

Indexing into large sparse matrix

NIcholas — Tue, 24 Mar 2009 20:44:02 -0400

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

Re: Indexing into large sparse matrix

Matt — Tue, 24 Mar 2009 21:50:18 -0400

"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) ?

Re: Indexing into large sparse matrix

Bruno Luong — Tue, 24 Mar 2009 22:10:05 -0400

"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

Re: Indexing into large sparse matrix

Bruno Luong — Tue, 24 Mar 2009 22:17:01 -0400

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

Bruno

Re: Indexing into large sparse matrix

NIcholas — Tue, 24 Mar 2009 22:32:01 -0400

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

Re: Indexing into large sparse matrix

Matt — Tue, 24 Mar 2009 22:46:01 -0400

"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)

Re: Indexing into large sparse matrix

Matt — Tue, 24 Mar 2009 22:48:02 -0400

"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...

Re: Indexing into large sparse matrix

Bruno Luong — Tue, 24 Mar 2009 22:55:18 -0400

"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

Re: Indexing into large sparse matrix

Matt — Tue, 24 Mar 2009 23:04:01 -0400

"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