I am doing research on a random-walk like problem. As a critical part of my solution, I need to invert a non-singular sparse matrix of size $n \times n$ and with $O(n)$ non-empty entries. I'm working over a sufficiently large field.
I'm looking for a fast algorithm to invert it (say, $O(n^2polylog(n))$). Is this achievable?