# When is it easy to invert a sparse matrix?

(Crossposted on cstheory.SE)

When is it easy to invert a sparse matrix? Specifically, I'm wondering about the cases in which matrix inversion has similar cost to sparse matrix multiplication, hence much lower cost than full matrix inversion.

If the pattern of non-zeros corresponds to a bounded tree-width graph, exact inversion is linear in the number of non-zeros.

For unbounded tree-width but diagonally dominant matrix, Gauss-Seidel and Jacobi algorithms converge exponentially fast. For a larger class of "walk-summable" matrices (which restricts magnitude of off-diagonal entries), Gaussian belief propagation converges exponentially fast (but gives a biased estimate of the inverse).

What are other interesting conditions for easy invertibility besides tree-width/diagonal dominance?

• Came across an interesting overview in Ch.1 rasmuskyng.com/rjkyng-dissertation.pdf, another easy case seems to be "symmetric M-matrix", case when $DMD$ is diagonally dominant for some diagonal $D$ – Yaroslav Bulatov Sep 22 at 19:23
• Are you using "invert" as in "solve a linear system with $A$" or as "compute the entries of the inverse of $A$"? – Federico Poloni Sep 22 at 20:11
• Either one -- since you can find inverse by solving k linear systems, having a fast linear solver will also give a fast inversion routine, and vica versa – Yaroslav Bulatov Sep 22 at 20:39
• by "fast" I mean that linear solver runtime is linear in the number of rows, while matrix inverse runtime is quadratic – Yaroslav Bulatov Sep 22 at 20:49
• As a point in terminology, you're really looking at families of matrices with varying sizes. So a family of matrices all of which have have eigenvalues equal to just the elements of the same, small set (in other words, with a relatively small number of eigenvalues but growing multiplicities) can be solved in $O(N)$. That's because for all of the typical iterative methods, the number of iterations necessary is bounded by the number of distinct eigenvalues. – Wolfgang Bangerth Sep 22 at 21:27