在查看系统的解决方案时，您会发现几乎所有的条目$x$尽管右侧是“稀疏的”，但它们是非零的。因此，无论您使用哪种算法，它都必须至少访问每个条目一次，因此人们不会期望您可以使用稀疏性来节省大量时间$b$.

例如，可以节省大量计算的右侧是特征向量的倍数$A$由于解决了

也就是说，每个满秩三对角方程组都可以求解$O(n)$. 使用多重网格，任何维度的泊松方程也是如此。

从您的问题中，我不清楚答案是具有理论意义还是实际意义。我会解决这两个问题。

为了使其具有实际重要性，您的系统需要有大量的方程，或者您需要多次求解。我怀疑简单地调用 Lapack 函数dptsv，该函数专门用于求解对称三对角系统，比在稀疏矩阵上调用 MATLAB 反斜杠要快得多。并且它将足够接近最佳时间方法，因此花费更多的精力是不值得的。然而，它并没有利用稀疏的右手边。该算法在Golub 和 Van Loan的第 4.3.6 节中进行了描述。总共$8n$需要浮点运算（触发器）；$3n$用于矩阵分解的触发器和$5n$触发器来计算给定右手边的解决方案。

Davis 的《稀疏线性系统的直接方法》一书的第 3 章 涉及求解左侧有三角矩阵的线性系统。他在这个主题上花费了相当多的时间，因为本书中大多数一般稀疏矩阵的方法都依赖于求解这些三角系统$n$次。他指出，如果每个三角形求解都假设右侧向量是密集的，那么这些方法将不切实际。所以他描述了一种线性求解算法，它允许一个通用的、稀疏的右手边向量并在函数中实现它 cs_spsolve。要使用本书中描述的软件求解对称正定系统，需要调用 以cs_chol分解稀疏矩阵，然后调用 2次cs_spsolve。这在理论上很有趣，但我怀疑它会导致比 Lapack 方法更少的计算时间，除非您正在求解许多右手边（例如，在网格中的不同点具有 delta 函数的许多情况）。