Re: Counting non-zero elements in sparse matrix

Adi wrote:
Does anyone have any ideas to solve the current problem:
I have a large NxM sparse matrix. I need to be able to count the
number of non-zero elements in sub-matrices of this matrix.

The sub-matrices are index by row and column indices of the original
matrix. For example, my new sub-matrix S may contain rows {1, 6, 9}
and cols {5, 9}. I now need to count the number of non-zero elements
in the intersection of the rows and cols contain in S, i.e. the cells
{1, 5}, {1, 9}, {6, 5}, ... etc

I need to do this calculation many times with many different -
possibly overlapping submatrices. Is there some smart solution I can
use that will perhaps buffer previous counts so as to reduce the
amount of counting required. (The original NxM matrix remains fixed).

Any ideas would be appreciated.

I'd use OCaml. Take their Map implementation and supplement it with the
split function from the Set implementation and inlined cardinality. Then
create sets of elements (mapping index to value) for each row and column.
Find the intersections you need with the "inter" function and count them
with the "cardinal" function.

An alternative is to store your sparse matrix in a hierarchical format like
a k-D tree and extract subs in O(log n) time. This requires more work
(because you can't reuse OCaml's containers) but it will be faster, maybe
10x faster.

--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?usenet
.

Relevant Pages

  • Re: Counting non-zero elements in sparse matrix
    ... I have a large NxM sparse matrix. ... number of non-zero elements in sub-matrices of this matrix. ... An alternative is to store your sparse matrix in a hierarchical format like ...
    (comp.programming)
  • Counting non-zero elements in sparse matrix
    ... I have a large NxM sparse matrix. ... The sub-matrices are index by row and column indices of the original ... and cols. ... (The original NxM matrix remains fixed). ...
    (comp.programming)
  • Re: add/remove elements in mex sparse format
    ... I add and remove elements in the sparse matrix by using indices as for example if ir has 6 non-zero elements and 3 is removed I write ... I got a bit curious here, how does MATLAB handle the above if A is sparse? ... Welcome to sparse mex programming. ...
    (comp.soft-sys.matlab)
  • Re: nnz in convariance of a sparse matrix
    ... > If a sparse matrix A has n nnz (number of non-zero elements), ... > nnz does A'A have, where A' is the transpose of A? ... to find the eigenvectors of the covariance matrix, ...
    (sci.math.num-analysis)
  • Re: Counting non-zero elements in sparse matrix
    ... number of non-zero elements in sub-matrices of this matrix. ... Well if you really have a big number of submatrices, ... non-zero elements of the intersections. ...
    (comp.programming)