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?

  • 1
    $\begingroup$ In practice or in theory? In theory, you can do it faster even for dense matrices - same complexity as matrix product, which is currently close to $O(n^{2.37})$. What you may want to ask is whether it can be done faster than that for sparse matrices, analogous to matrix product (sparse matrix product can be done trivially in $O(n^2)$ time). $\endgroup$ – Joshua Grochow May 19 '19 at 13:47
  • $\begingroup$ @JoshuaGrochow Oh, I totally forgot about that. I'll edit my problem description then. $\endgroup$ – newbie May 19 '19 at 13:48
  • $\begingroup$ I think you should specify a computational model and a precision parameter. $\endgroup$ – Aryeh May 19 '19 at 17:24
  • $\begingroup$ @Aryeh: The OQ says "under a sufficiently large field", which to me means the goal is an algorithm that will work over (sufficiently large) finite fields (which would presumably work over other fields as well). Over finite fields, precision is no issue. The computational model could have an effect, e.g. BSS / algebraic circuits vs Boolean, but at the level of this question I'm guessing nothing beyond algebraic is known. $\endgroup$ – Joshua Grochow May 19 '19 at 20:24
  • 2
    $\begingroup$ If your matrix is Laplacian, you might check out Rasmus Kyng's thesis: rasmuskyng.com/rjkyng-dissertation.pdf and his later papers on Sparse Gaussian Elimination. $\endgroup$ – Thomas Ahle May 20 '19 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.