<p>Jacobi or Gauss-Seidel are not really state of the art for solving systems of linear equations. It is more done by preconditioned conjugated gradient (for symmetric positive semi-definite matrices) and preconditioned (F)GMRES (or other Krylov subspace methods) for arbitrary matrices.</p>
<p>The crucial part here is the preconditioner. There was recently (=21th century) huge progress with very efficient preconditioners for Laplacian systems. In <a href="https://arxiv.org/abs/1705.02944" rel="nofollow noreferrer">Hardness Results for Structured Linear Systems</a> by Rasmus Kyng and Peng Zhang, it is shown</p>
<blockquote>
<p>that if the nearly-linear time solvers for Laplacian matrices and their generalizations can be extended to solve just slightly larger families of linear systems, then they can be used to quickly solve all systems of linear equations over the reals.</p>
</blockquote>
<p>They go on to say:</p>
<blockquote>
<p>This result can be viewed either positively or negatively: either we will develop nearly-linear time algorithms for solving all systems of linear equations over the reals, or progress on the families we can solve in nearly-linear time will soon halt.</p>
</blockquote>
<p>But even beyond such deep theory, one can say something about the computational cost of a preconditioner and its efficiency. A matrix is hard to solve, if its condition number is big. The task of the preconditioner is to reduce the condition number, by approximately inverting the matrix. The (asymptotic) computational cost (vs efficiency) can estimated based on separators of the sparse matrix. For example, to separate a N x N x N grid in 3D, you need a separator of size O(N^2). If you would not approximate the system on the separator, you would get a full matrix of size(N^2), i.e. N^4 non-zero entries. So you need to approximate the clique graph on the separator with a sparse (directed) graph, probably an extender graph. One fast preconditioner algorithm for Laplacian systems approximates the clique (among the neighbors of the eliminated node, which has to be added to the graph) in each elimination step by a tree. This is good enough to keep the computational cost under control. The efficiency of this preconditioner in reducing the condition number is also often extremely good in practice, but proving this theoretically would still be a nice achievement.</p>
<p>A recent result on fast solving sparse linear systems replaced the Krylov subspace methods mentioned above by &quot;an efficient, randomized implementation of the block Krylov method&quot;: <a href="https://arxiv.org/abs/2007.10254" rel="nofollow noreferrer">Solving Sparse Linear Systems Faster than Matrix Multiplication</a> by Richard Peng and Santosh Vempala. Even so the paper title says &quot;solving ... faster than matrix multiplication,&quot; this does not answer the question asked here, because the paper means dense matrix multiplication, but the question here is about sparse matrix multiplication.</p>

CC BY-SA 4.0
2020-09-22T23:20:45.937Z
Interesting, sounds like another application of tree decomposition. Is this something that applies to laplacians of grid graphs, or does the graph need to be close to small-treewidth graph?
Yaroslav Bulatov
CC BY-SA 4.0
2020-09-22T23:30:57.890Z
@YaroslavBulatov This applies to laplacians of arbitrary graphs, no need for small treewidth. And the tree does not relate to treewidth either. A tree is just the sparsest graph possible in this context which still has a chance to approximate a clique. (And you could use the same strategy for an incomplete LU decomposition of an arbitrary sparse matrix, only I guess it no longer reduce the condition number so extremely well. But it should still work much better than a normal incomplete LU decomposition.)
Thomas Klimpel
CC BY-SA 4.0
2020-09-22T22:43:12.293Z
2020-09-22T22:43:12.293Z
Thomas Klimpel
<p>Are cases where numeric inversion of a sparse matrix is known to be harder than sparse matrix multiplication?</p>
<p>In practice, sparse matrix inversion is done with methods like Jacobi or Gauss-Seidel, which  give a good estimate after a small number of sparse matrix multiplications, when they converge.</p>
<p>However such methods fail to converge when off-diagonal entries are large compared to diagonal entries. I'm curious if this is a limitation of those methods, or reflects a fundamental difficulty of the task.</p>

<linear-algebra><sparse-matrix><linear-equations>
When is it hard to invert a sparse matrix?
Yaroslav Bulatov
# When is it hard to invert a sparse matrix?

(Asked by: username_0 on 2020-09-22)

Are cases where numeric inversion of a sparse matrix is known to be harder than sparse matrix multiplication?

In practice, sparse matrix inversion is done with methods like Jacobi or Gauss-Seidel, which give a good estimate after a small number of sparse matrix multiplications, when they converge.

However such methods fail to converge when off-diagonal entries are large compared to diagonal entries. I'm curious if this is a limitation of those methods, or reflects a fundamental difficulty of the task.

**Tags:** linear-algebra, sparse-matrix, linear-equations

---

## 1 answers

### Answer by username_1 on 2020-09-22. Score: 2 | Accepted answer

Jacobi or Gauss-Seidel are not really state of the art for solving systems of linear equations. It is more done by preconditioned conjugated gradient (for symmetric positive semi-definite matrices) and preconditioned (F)GMRES (or other Krylov subspace methods) for arbitrary matrices.

The crucial part here is the preconditioner. There was recently (=21th century) huge progress with very efficient preconditioners for Laplacian systems. In [Hardness Results for Structured Linear Systems](https://arxiv.org/abs/1705.02944) by Rasmus Kyng and Peng Zhang, it is shown

> that if the nearly-linear time solvers for Laplacian matrices and their generalizations can be extended to solve just slightly larger families of linear systems, then they can be used to quickly solve all systems of linear equations over the reals.

They go on to say:

> This result can be viewed either positively or negatively: either we will develop nearly-linear time algorithms for solving all systems of linear equations over the reals, or progress on the families we can solve in nearly-linear time will soon halt.

But even beyond such deep theory, one can say something about the computational cost of a preconditioner and its efficiency. A matrix is hard to solve, if its condition number is big. The task of the preconditioner is to reduce the condition number, by approximately inverting the matrix. The (asymptotic) computational cost (vs efficiency) can estimated based on separators of the sparse matrix. For example, to separate a N x N x N grid in 3D, you need a separator of size O(N^2). If you would not approximate the system on the separator, you would get a full matrix of size(N^2), i.e. N^4 non-zero entries. So you need to approximate the clique graph on the separator with a sparse (directed) graph, probably an extender graph. One fast preconditioner algorithm for Laplacian systems approximates the clique (among the neighbors of the eliminated node, which has to be added to the graph) in each elimination step by a tree. This is good enough to keep the computational cost under control. The efficiency of this preconditioner in reducing the condition number is also often extremely good in practice, but proving this theoretically would still be a nice achievement.

A recent result on fast solving sparse linear systems replaced the Krylov subspace methods mentioned above by "an efficient, randomized implementation of the block Krylov method": [Solving Sparse Linear Systems Faster than Matrix Multiplication](https://arxiv.org/abs/2007.10254) by Richard Peng and Santosh Vempala. Even so the paper title says "solving ... faster than matrix multiplication," this does not answer the question asked here, because the paper means dense matrix multiplication, but the question here is about sparse matrix multiplication.

> **Comments:**
> **username_0**: Interesting, sounds like another application of tree decomposition. Is this something that applies to laplacians of grid graphs, or does the graph need to be close to small-treewidth graph?  
> **username_1**: @YaroslavBulatov This applies to laplacians of arbitrary graphs, no need for small treewidth. And the tree does not relate to treewidth either. A tree is just the sparsest graph possible in this context which still has a chance to approximate a clique. (And you could use the same strategy for an incomplete LU decomposition of an arbitrary sparse matrix, only I guess it no longer reduce the condition number so extremely well. But it should still work much better than a normal incomplete LU decomposition.)  

---

