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

Question

我试图找出解决五对角矩阵的最佳方法。有没有比高斯消去法更快的东西？

Answer 1

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

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