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
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.