Re: Counting non-zero elements in sparse matrix

On May 7, 3:36 am, Jon Harrop <j...@xxxxxxxxxxxxxxxxx> wrote:
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.

The day is fast approaching when I spend the time to learn OCaml.


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.

You've given me the idea that perhaps its not a matrix that i need at
all but simply a tree that contains counts of matrices of various
sizes. I've used an AD-Tree in the past which seems to fit the bill -
once I've pre-processed the data - I should be able to get counts in
constant time.

Thanks for the help.

Adi

--
Dr Jon D Harrop, Flying Frog Consultancy
The F#.NET Journalhttp://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. ... The sub-matrices are index by row and column indices of the original ... An alternative is to store your sparse matrix in a hierarchical format like ...
    (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)
  • Re: Sparse Matrix Calculation exceed full matrix times
    ... Well, I obviously do not fill all the zeros, just some, ... Do not just set elements in a sparse matrix ...
    (comp.soft-sys.matlab)
Loading