Services & ResourcesWolfram ForumsMathGroup Archive

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

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>