Efficient algorithm to identify basis of a sparse matrix over the ground field(2)

14 Views Asked by At

As the title suggests, I'm trying to identify the basis of a large sparse matrix of dimensions m x n, over the ground field(2). I do not care about practicality, my goal is to lower the exponent. Current best algorithms can solve it in O($n^w$) complexity, where w is the Matrix multiplication exponent. However this algorithm is applicable to any matrix. I wish to obtain a faster algorithm for sparser matrices, where the number of non zero entries is O(n).