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

*To*: mathgroup at smc.vnet.net*Subject*: [mg56846] Re: How to quickly find number of non-zero elements in sparse matrix rows?*From*: Paul Abbott <paul at physics.uwa.edu.au>*Date*: Sat, 7 May 2005 15:35:07 -0400 (EDT)*Organization*: The University of Western Australia*References*: <d5hum0$k03$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

In article <d5hum0$k03$1 at smc.vnet.net>, 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}]]; Alternatively, sa = SparseArray[{{i_, i_} -> 1}, {200000, 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? Here is one suggestion: For the first 100 entries, the following is essentially instantaneous (only one call to ArrayRules). Most[Length /@ Split[ArrayRules[sa[[Range[100]]]], #1[[1,1]] == #2[[1,1]] & ]] // Timing The test #1[[1,1]] == #2[[1,1]] & is used by Split to start a new List whenever the row index changes. Most is required to drop the default case, {_, _} -> 0. For the full array, the following is quite reasonable: Most[Length /@ Split[ArrayRules[sa], #1[[1,1]]==#2[[1,1]]&]]; //Timing In the advanced documentation for Linear Algebra -- there is a link to this from the Help Browser entry for SparseArray -- you will find that SparseArray uses the Compressed Sparse Row (CSR) format as an internal storage format. You can view this information using InputForm. For example, SparseArray[{{1, 1} -> 1, {2, 3} -> 2, {2, 2} -> 1}, {3, 4}]] // InputForm The 4-th part of the data structure records the cumulative sum of non-zero entries. However, there seems to be no simple way to access this information. Usually, for special formats you can use Part to extract such information but Part is interpreted by SparseArray, circumventing this. Cheers, Paul -- Paul Abbott Phone: +61 8 6488 2734 School of Physics, M013 Fax: +61 8 6488 1014 The University of Western Australia (CRICOS Provider No 00126G) AUSTRALIA http://physics.uwa.edu.au/~paul http://InternationalMathematicaSymposium.org/IMS2005/

**Follow-Ups**:**Re: Re: How to quickly find number of non-zero elements in sparse matrix rows?***From:*Chris Chiasson <chris.chiasson@gmail.com>