Re: [ublas] Parsing Sparse Matrix to Get JA, IA, A Vector

Subject: Re: [ublas] Parsing Sparse Matrix to Get JA, IA, A Vector
From: Carl Barron (cbarron413_at_[hidden])
Date: 2009-08-06 22:48:00

On Aug 6, 2009, at 9:49 PM, Peverall Dubois wrote:

> Does boost has a library to parse a sparse matrix
> to get the index the non-zero element value?
>
> E.g. given this matrix:
>
> 1 2 0 0
> 0 3 9 0
> 0 1 4 0
>
> We hope it to return
> A  = [ 1 2 3 9 1 4 ]
> IA = [ 1 3 5 7 ]
> JA = [ 1 2 2 3 2 3 ]
>
> Let NNZ denote the number of nonzero entries of Matrix. The first
> array is A, which is of length NNZ, and holds all nonzero entries of M
> in left-to-right top-to-bottom order. The second array is IA, which is
> of length m + 1 (i.e., one entry per row, plus one). IA(i) contains
> the index in A of the first nonzero element of row i. Row i of the
> original matrix extends from A(IA(i)) to A(IA(i+1)-1). The third
> array, JA, contains the column index of each element of A, so it also
> is of length NNZ.
>
> Is there any implementation for handling such a large matrix to give
> us A, IA and JA, without having have to slurp all the files into RAM?
> Because the actual dimension is very large 10^6 to 10^7.

   M has n_rows and n_cols and nzero non-zero elements.

   if the matrix M is read in row major order then its simple linear  
sweep of the array M
keeping track of the row and col being read and filling A,JA,IA in a  
linear fashion.

   if the matrix is read col. major order then let IA do double duty  
first holding the i subscript
of the nonzero entries and later the beginning of the rows;
     sweeping the matrix store only the non-zero entries in A, the i  
subscript in IA and the j subscript
in JA.
    then sort the three vectors on with key IA in ascending order.  
1,2,3,etc.
    now A and JA are done,

    convert the sequence of equal row subscripts to where the sequence  
begins,producing IA.

  this requires  IA to have a dimension of max (n_rows + 1,nzero) at  
least until this is done