（交叉发布在ctheory.SE上）
什么时候可以轻松反转稀疏矩阵？具体来说，我想知道矩阵求逆的成本与稀疏矩阵乘法相似的情况，因此成本比全矩阵求逆低得多。
如果非零的模式对应于有界树宽图，则精确反转在非零的数量上是线性的。
对于无界树宽但对角占优的矩阵，Gauss-Seidel 和 Jacobi 算法以指数速度快速收敛。对于更大类的“可步行求和”矩阵（它限制了非对角线条目的大小），高斯置信传播以指数速度快速收敛（但给出了逆向的有偏估计）。
除了树宽/对角线优势之外，还有哪些其他有趣的条件可以轻松实现可逆性？
一种这样的情况是稀疏矩阵是带状的。例如，可以使用 Thomas 算法在线性时间内求解三对角线性系统。对于小带宽，您可以找到线性时间成本的算法。请注意，随着带宽的增长，隐藏系数也会增长。
关于这个主题的文献很活跃，据我所知，有很多特征，其中一些你已经找到了。也许您应该将引用请求添加为标签。
有很多方法可以解决具有稀疏矩阵的系统，因此没有办法明确地回答这个问题并穷尽所有可能性。不过，我会添加 Krylov 方法作为答案。许多 Krylov 方法在适当的条件下取得了快速的结果。
Krylov 方法执行良好的条件之前已在此处询问过。每个 Krylov 求解器都有点不同，但我将以 GMRES 为例。
对于 GMRES，如果您的输入矩阵具有以下属性：
那么无论右侧向量如何，GMRES 都可能会非常迅速地收敛。请注意，条件 (1) 到 (3) 实际上根本没有说明矩阵的稀疏性，但通常由于稀疏矩阵向量积很便宜，GMRES 算法可以很好地适用于稀疏情况。