有很多关于如何使用 A 的稀疏模式来解决问题的信息. 但是我找不到太多关于使用 b 的稀疏模式的信息。让我举一个具体的例子：
让我们假设 A 是一个大矩阵 （) 具有已知的稀疏模式。现在让我们假设我想解决以下形式的重复线性系统其中是一个只有一个非零条目的列向量。（这似乎是与计算矩阵逆的某些给定列类似的问题）。
我知道我可以通过直接或迭代求解器计算线性系统的解，同时利用 A 的已知稀疏结构（如果需要，可以预先计算），但是呢？? 这样做感觉就像我要花费与解决一样多的计算时间其中 c 是一个完整的向量，但这里只有 b 的一个元素是非零的，有没有办法专门利用它？
例如，如果使用直接 LU 分解，我可以想办法：如果，例如，最后一个元素等于 1 的单位列向量（我们总是可以在 A 上应用排列以使其成为我相信的方式），然后是前向替换实际上只包含一个操作。我认为可能还有其他我不知道的像这样的“技巧”，希望包含在某些软件包中（我个人喜欢使用 petsc），因此任何指向该主题参考的链接将不胜感激。
任何“有趣”矩阵的逆矩阵都是稠密的，这是一个基本的直觉。这意味着即使稀疏，会很稠密。因此，在最好的情况下（使用直接求解器），您可以通过在求解中使用稀疏性来获得 2 倍的加速，但分解不会更快。
使用迭代求解器，预处理器要么尽可能快地在全局范围内传播信息（立即破坏稀疏性），要么迭代将非常缓慢地收敛，而向量在收敛之前仍然变得密集。即使不考虑实现性能，这也不会带来什么好处。
如果您只需要逆向或对角线的几个条目，则像SelInv这样的算法会智能地携带来自多面求解的因子，而不是计算逆向的显式密集表示。（这个想法很老，但最近才用通用语言重新表述。）还有一些探测方法来估计属性，比如逆的踪迹。
首先让我们排除像 Krylov 子空间方法这样的迭代方法。如果你形成产品,等，并且它们具有可预测的稀疏模式，那么您的矩阵有一些可简化的属性（它有一些与其余部分解耦的块，或类似的东西）。通常，这些产品不会随着迭代的进行而保持稀疏性，并且计算残差如会破坏中间体的稀疏性。这里没有运气。
对于涉及矩阵分解的直接方法，您可能已经在利用稀疏性分解阶段。正如你所提到的，稀疏模式可以显着降低反向替代的成本（它是在哪里是非零的数量. 这已经是最佳的了，所以看起来你在这里也不能做得更好。
现在，正如您所指出的，您基本上只对一些选定的列感兴趣. 我所知道的唯一用于执行此操作的算法，例如 SelInv，需要矩阵分解，因此它并不比直接方法好。
分解和对于像 UMFPACK 这样的稀疏直接求解器来说，这甚至可能是一个问题。如果你想利用稀疏的优势你必须计算然后计算一个非零条目的可达性集在由定义的图上. 这样你就可以解决然后计算非零元素的可达集在由定义的图上并解决这样。Tim Davis 的“稀疏线性系统的直接求解”一书中描述了一种易于理解的计算这些集合的方法。