9
$\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$
5
  • $\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$ Commented Sep 22, 2020 at 19:23
  • 2
    $\begingroup$ Are you using "invert" as in "solve a linear system with $A$" or as "compute the entries of the inverse of $A$"? $\endgroup$ Commented Sep 22, 2020 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$ Commented Sep 22, 2020 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$ Commented Sep 22, 2020 at 20:49
  • 3
    $\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$ Commented Sep 22, 2020 at 21:27

2 Answers 2

4
$\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.

$\endgroup$
2
  • 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$ Commented Sep 23, 2020 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$ Commented Sep 23, 2020 at 18:28
1
$\begingroup$

There are many ways to solve systems with sparse matrices, so there is no way to answer this definitively and exhaust all possibilities. I'll add Krylov methods as one answer though. Many Krylov methods achieve fast results under the right conditions.

The conditions for Krylov methods to perform well have been asked here before. Every Krylov solver is a little bit different, but I'll give GMRES as an example.

For GMRES if your input matrix has the following properties:

  1. Normal (or approximately normal)
  2. Eigenvalues not too close to 0
  3. Eigenvalues clustering (easily identified "groups" of eigenvalues all close together)

then GMRES will likely converge very rapidly regardless of the right-hand-side vector. Note that the conditions (1) through (3) actually don't say anything about sparsity of the matrix at all, but usually since sparse matrix-vector product is cheap the GMRES algorithm can be well suited to the sparse case.

$\endgroup$

Your Answer

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

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