language-agnostic - 求解带对角矩阵的最佳算法是什么？

Question

我试图找出解决五对角矩阵的最佳方法。有什么比高斯消除更快的吗？

Answer 1

您应该对矩阵进行 LU 或 Cholesky 分解，具体取决于您的矩阵是否是 Hermitian 正定矩阵，然后用因子进行反向替换。这本质上只是高斯消元法，但往往具有更好的数值特性。我推荐使用 LAPACK，因为这些实现往往是最快和最健壮的。查看_GBSV例程，其中空格是 s、d、c、z 之一，具体取决于您的号码类型。

编辑：如果您询问是否有比因子/求解（高斯消除）方法更快的算法，则不存在。带状矩阵的专用分解例程需要大约 4n*k^2 次操作（k 是带宽），而反向替换需要大约 6*n*k 次操作。因此，对于固定带宽，您不能比 n 中的线性时间做得更好。