MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: How to quickly find number of non-zero elements in sparse matrix rows?


Matt,
Try this:

<<LinearAlgebra`MatrixManipulation`
MatrixPlot[sa=SparseArray[Table[{i+20,i+20}\[Rule]1,{i,200}]]];
arules=First@First@##&/@Most@ArrayRules[sa];
<<Statistics`DataManipulation`
frules=Append[Rule@@@Reverse/@Frequencies@arules,_?NumericQ->0];
populationlist=(Range@Length@sa)/.frules

Regards,

On 5/7/05, Matt Pharr <matt at pharr.org> wrote:
> 
> I have a sparse matrix, roughly 200k by 200k, with about .01% of the
> entries non zero, represented with SparseArray.  I'd like to reasonably
> efficiently generate a 200k-long list where each element is the number of
> non-zero entries in the corresponding row of the matrix.  I haven't been
> able to figure out a quick way to do this.
> 
> One approach I've tried is the following (using a made up SparseArray of
> an identity matrix to illustrate the point):
> 
> In[76]:= sa = SparseArray[Table[{i,i}\[Rule]1, {i, 200000}]];
> In[77]:= rowLen[sa_, r_] :=  Length[ArrayRules[Take[sa, {r}]]]-1
> 
> However, it's quite slow--about 1/10 of a second for each value computed
> (on a 1GHz Mac G4)
> 
> In[80]:= Table[rowLen[sa,i], {i,100}] // Timing
> Out[80]=
> {12.4165 Second,{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
>     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
>     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}
> 
> I've got to assume that there's an efficient way to do this--does anyone
> have any suggestions?
> 
> thanks,
> -matt
> --
> Matt Pharr    matt at pharr.org    <URL:http://graphics.stanford.edu/~mmp>
> =======================================================================
> In a cruel and evil world, being cynical can allow you to get some
> entertainment out of it. --Daniel Waters
> 
> 


-- 
Chris Chiasson
http://chrischiasson.com/
1 (810) 265-3161


  • Prev by Date: Re: RC circuit
  • Next by Date: Re: letrec/named let
  • Previous by thread: How to quickly find number of non-zero elements in sparse matrix rows?
  • Next by thread: Re: How to quickly find number of non-zero elements in sparse matrix rows?