How to find non-zero elements of matrix A^T * A where A is sparse (crs/ccs) matrix?

I have very sparse large matrix A (A is a compressed row storage)

I want to perform some computations over B = A^T * A matrix. But B should be sparse too due sparsity of A.

How i can compute "mask" of B? "Mask" is column indices and row offsets of compressed row storage.

Only way which i see is to iterate over rows in nested loops (by i and j) and check (i, j) element of B as non-zero if rows i and j of A have at least one common non-zero column. But i think is slow.

PS Sorry for my poor english

Answers


I think you could do it in O(n^2), with n - number of nonzero elements in the matrix A.

Consider Bij=sum Aki*Akj, Bij could be only then nonzero if there is a k with Aki and Akj - nonzero.

Iterating through all nonzero elements of A and through the nonzero elements of the kth row of A = Ak (consecutive access, one element in the row after another, I assume compressed row storage (crs) - for ccs you need to iterate over columns) yields the following algorithm:

for (k, i) in indices(nonzero(A)):
    for j in indices(nonzero(Ak)):
      Bij=nonzero

As both for loops need only to touch the nonzero elements of A in row order (this is crucial!) and the operation Bij=nonzero costs O(1), if you use for example a hash set or a boolean field, the resulting running time must be O(n^2).

With A=[1,..,1; 0,..,0; ...; 0, ..,0] i.e. a matrix with the first row of nonzero element you can see, that there is really a worst case, which needs n^2 operations. For example:

A=[1,1;0,0] -> A^T=[1,0;1,0]
B=A^t*A=[1,1;1,1]

I'm not sure it's different from your approach, but I don't think there is something much faster, if you have no additional information about the form of the matrix A.


Need Your Help

Twitter bootstrap margin ul tag

css ruby-on-rails twitter-bootstrap margin

I am using Twitter Bootstrap, but can't understand

Socket remains open after program has closed (C++)

c++ sockets bind

I'm currently writing a small server application, and my problem is, that when I close my app (or better, press the terminate button in eclipse), the socket sometimes stays open, so when I execute ...