SPD 问题的直接求解器的复杂性主要取决于底层图的属性。如果您的矩阵来自椭圆方程的离散化，那么它基本上取决于支持离散化的网格/结构。这是因为直接方法基于消除未知数的事实，这些未知数可以生成填充（即更密集的子图），因此在前面的消除中工作更多。

例如，如果您的矩阵图是一棵树，您可以一一消除未知数，直接求解器的复杂度为$O(n)$其中是图中的节点数。

但是，如果该图是平面图（您可以在 2d 平面上绘制的图），Tarjan 和 Rose（1979）的一个众所周知的结果表明复杂度为$O(n^{3/2})$. 由于它们的结构，这些图提供了快速消除并且是直接方法的良好候选者。

然而，在光谱的另一边，有一些图的复杂性是最大的，就像我们得到的完整图一样$O(n^3$)，它们对应的矩阵是稠密矩阵。

简单的答案是带宽矩阵的高斯消除（不旋转）$b$需要$O(nb^2)$操作，而不利用进一步的稀疏特性。

一般来说，使用直接算法很难进一步利用带宽内的稀疏性；经典的高斯消元法会很快填满带宽。

由于矩阵是 SPD，所以高斯消元将是稳定的，无需旋转。