求解帶對角矩陣的最佳算法是什麼？

Question

我試圖找出解決五邊形矩陣的最佳方法。有沒有比高斯消除更快的東西？

Answer 1

您應該對矩陣進行LU或Cholesky分解，具體取決於您的矩陣是否爲Hermitian正定，然後用因子進行替換。這實質上只是高斯消除，但往往具有更好的數值特性。我推薦使用LAPACK，因爲這些實現往往是最快和最強大的。查看_GBSV例程，其中空格是s，d，c，z之一，具體取決於您的號碼類型。

編輯：如果您詢問是否有比算法/求解（高斯消元）方法更快的算法，則不存在。一個帶狀矩陣的專門分解例程需要大約4n * k^2次操作（k是帶寬），而後向置換需要大約6 * n * k次操作。因此，對於固定帶寬，你不可能比n中的線性時間更好。