4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Yaroslav Bulatov Sep 22 at 19:23
  • $\begingroup$ Are you using "invert" as in "solve a linear system with $A$" or as "compute the entries of the inverse of $A$"? $\endgroup$ – Federico Poloni Sep 22 at 20:11
  • $\begingroup$ 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 $\endgroup$ – Yaroslav Bulatov Sep 22 at 20:39
  • $\begingroup$ by "fast" I mean that linear solver runtime is linear in the number of rows, while matrix inverse runtime is quadratic $\endgroup$ – Yaroslav Bulatov Sep 22 at 20:49
  • 2
    $\begingroup$ 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. $\endgroup$ – Wolfgang Bangerth Sep 22 at 21:27
3
$\begingroup$

One such case is if the sparse matrix is banded. For example, tridiagonal linear systems can be solved in linear time using Thomas' algorithm. For small bandwidths, you can find an algorithm of linear time cost. Note that as the bandwidth grows, the hidden coefficient grows too.

The literature on the topic is active and there are many characterizations as far as I see, some of which you have already found. Maybe you should add reference-request as a tag.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Yeah, banded is a special case of "small treewidth" graph, which is equivalent to the system having a sparse Cholesky factorization. A generic approach for solving such systems is to find such factorization, I've made some illustrations of how to do this here -- mathematica-bits.blogspot.com/2011/02/… $\endgroup$ – Yaroslav Bulatov Sep 23 at 18:15
  • $\begingroup$ Thanks for the reference to Thomas' algorithm, didn't know about this name, but it seems to fit the mold. I do wonder how many solvers for sparse linear systems are basically rediscoveries of the tree decomposition (small treewidth seems more general than small bandwidth) ... $\endgroup$ – Yaroslav Bulatov Sep 23 at 18:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.