(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?