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/

```

• Prev by Date: Re: Re: named pattern variable scoped as global, should be local
• Next by Date: Re: how call a function by same name in 2 different contexts?
• Previous by thread: Re: How to quickly find number of non-zero elements in sparse matrix rows?
• Next by thread: Re: Re: How to quickly find number of non-zero elements in sparse matrix rows?