5
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 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, 2019 at 13:47
  • $\begingroup$ @JoshuaGrochow Oh, I totally forgot about that. I'll edit my problem description then. $\endgroup$
    – newbie
    May 19, 2019 at 13:48
  • $\begingroup$ I think you should specify a computational model and a precision parameter. $\endgroup$
    – Aryeh
    May 19, 2019 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, 2019 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, 2019 at 14:11

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.