<p>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 <span class="math-container">$n \times n$</span> and with <span class="math-container">$O(n)$</span> non-empty entries. I'm working over a sufficiently large field.</p>

<p>I'm looking for a fast algorithm to invert it (say, <span class="math-container">$O(n^2polylog(n))$</span>). Is this achievable?</p>

CC BY-SA 4.0
2019-05-19T13:47:05.667Z
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).
Joshua Grochow
CC BY-SA 4.0
2019-05-19T13:48:33.410Z
@JoshuaGrochow Oh, I totally forgot about that. I'll edit my problem description then.
newbie
CC BY-SA 4.0
2019-05-19T17:24:54.623Z
I think you should specify a computational model and a precision parameter.
Aryeh
CC BY-SA 4.0
2019-05-19T20:24:26.047Z
@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.
Joshua Grochow
CC BY-SA 4.0
2019-05-20T14:11:50.637Z
If your matrix is Laplacian, you might check out Rasmus Kyng's thesis: http://rasmuskyng.com/rjkyng-dissertation.pdf and his later papers on Sparse Gaussian Elimination.
Thomas Ahle
CC BY-SA 4.0
2019-05-21T00:43:28.977Z
@ThomasAhle I think the problem discussed in that thesis is just roughly what I'm working on. However, I'm not looking for any approximations here since I'm working under a finite field.
newbie
<ds.algorithms><linear-algebra>
Is there a fast algorithm for inverting a sparse matrix?
newbie
# Is there a fast algorithm for inverting a sparse matrix?

(Asked by: username_0 on 2019-05-19)

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?

**Tags:** ds.algorithms, linear-algebra

> **Comments:**
> **username_1**: 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).  
> **username_0**: @JoshuaGrochow Oh, I totally forgot about that. I'll edit my problem description then.  
> **username_2**: I think you should specify a computational model and a precision parameter.  
> **username_1**: @username_2: 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.  
> **username_3**: If your matrix is Laplacian, you might check out Rasmus Kyng's thesis: http://rasmuskyng.com/rjkyng-dissertation.pdf and his later papers on Sparse Gaussian Elimination.  
> **username_0**: @ThomasAhle I think the problem discussed in that thesis is just roughly what I'm working on. However, I'm not looking for any approximations here since I'm working under a finite field.  

---

## 0 answers

