How to iterate non-zeroes in a sparse matrix in Ch

问题:

I have a matrix A still hanging around. It's large, sparse and new symmetric. I've created a sparse domain called spDom that contains the non-zero entries. Now, I want to iterate along row r and find the non-zero entries there, along with the index. My goal is to build another domain that is essentially row r's non-zeroes.

回答1:

Here's an answer that will work with Chapel 1.15 as long as you're willing to store your sparse domain/array in CSR format:

First, I'll establish my (small, non-symmetric) sparse matrix for demonstration purposes:

use LayoutCS;                               // use the CSR/CSC layout module

config const n = 10;                        // declare problem size
const D = {1..n, 1..n};                     // declare dense domain                                  
var SD: sparse subdomain(D) dmapped CS();   // declare sparse subdomain                 

// populate sparse domain with some indices                                                       
SD += (1,1);
SD += (1,n/2);
SD += (2, n/4);
SD += (2, 3*n/4);
SD += (n/2, 1);
SD += (n/2, n);

var A: [SD] real;                          // declare sparse array                                  

forall (i,j) in SD do                      // initialize sparse array values                       
  A[i,j] = i + j/10.0;

My solution relies on an undocumented iterator on sparse CS* domains named dimIter() which can be used to iterate over the dimension that's stored consecutively in memory (so rows for CSR and columns for CSC). dimIter() takes two arguments: the dimension to iterate over (1=rows, 2=columns) and the index in the other dimension. Thus, to iterate over the rows that I've defined above, I could do:

for r in 1..n {
  writeln("row ", r, " contains elements at:");
  for c in SD.dimIter(2, r) do
    writeln("  column ", c, ": ", A[r,c]);
}

For the sparse matrix I show above, this yields:

row 1 contains elements at:
  column 1: 1.1
  column 5: 1.5
row 2 contains elements at:
  column 2: 2.2
  column 7: 2.7
row 3 contains elements at:
row 4 contains elements at:
row 5 contains elements at:
  column 1: 5.1
  column 10: 6.0
row 6 contains elements at:
row 7 contains elements at:
row 8 contains elements at:
row 9 contains elements at:
row 10 contains elements at:

We're interested in generalizing the dimIter() iterator and making it part of the standard sparse domain/array interface, but haven't done so yet due to (a) questions about how to generalize it to n-dimensional sparse arrays and (b) questions about whether we need to support inefficient iteration directions (e.g., should one be able to iterate over columns of CSR or rows of CSC given the expense?)