What is fastest (possible amenable to multithreading as well) way to identify which columns in a matrix are "connected", where "connected" is defined as follows:
at least one non-zero row in column "x" has a non-zero entry in the same row in another column in the matrix. (This process repeats, obviously, until there are no more columns that can be "connected" to each other.)
The matrix is 99.9% sparse and is approximately 1 million columns by 10 million rows.
(FYI: I'm not even too sure what branch of mathematics this falls under, though I suspect it's somewhere in graph theory.)
Create a union-find structure, with columns being elements. Now run the following algorithm: for each row with nonzero elements, take first nonzero element of this row, find a representative of the column containing this element in your union-find structure, and merge remaining nonzero columns in this row with it.
This algorithm runs in $O(n \cdot \alpha(n)))$ time, where $n$ is number of non-zero entries in your matrix. This algorithm can easily be parallelized (e.g. by having each thread consider each row separately), assuming you have parallel union-find implementation, which can be found e.g. in Anderson, Richard J.; Woll, Heather (1994). Wait-free Parallel Algorithms for the Union-Find Problem. 23rd ACM Symposium on Theory of Computing. pp. 370–380.