Recommendations for finding pivot rows of a matrix?

[Sucheer Maddury]

Hello,

I have a large, highly sparse m * k matrix M over GF2, where m is ~3-5 times larger than k. M is guaranteed to have a rank of k, which means somewhere in M, there are k pivot rows such that if we just extract those k rows exactly as they are, we will have a k * k nonsingular matrix.

Approximately, k ~ 10000, m ~ 40000, with ~20 nnz/row. 

I want to find the indices of k such pivot rows (any solution is fine). I have tried methods like QLUPin, but have not been able to figure out how to recover the row indices for the ORIGINAL matrix. The final trimmed matrix must have the entires of the rows appear in their original orders, ie they need to be the original rows. 

Any help would be appreciated.