有沒有可能在線性時間內反演對稱帶狀（7對角線）矩陣？

Question

我需要反轉p×p對稱帶狀hessian矩陣H，它有7個對角線。 p可能非常高（= 1000或10000）。可以認爲H^{ - 1}是帶邊的，因此，我不需要計算完整的逆矩陣，而是計算它的近似值。 （例如，可以假設有11或13對角線。） 我正在尋找一種不意味着並行化的方法。

有沒有可能在線性時間內用R建立這樣的算法？

謝謝你的幫助。

Answer 1

就我所知，沒有線性時間算法。 但是你不是完全沒有希望：

1. 你的矩陣是不是真的那麼大，所以使用相對優化的實現可能是相當快的p < 10K。例如，一個密集的 LU分解需要最多O(p^3)，p = 1000，這可能需要不到一秒鐘。在實踐中，稀疏矩陣的實現應該取得更好的性能，利用稀疏性;
2. 你真的，真的，真的需要計算逆？經常明確地計算逆可以通過求解等價的線性系統來代替;利用諸如迭代求解器（例如conjugate gradient）的一些方法求解線性系統顯着更高效，因爲源矩陣的稀疏模式被保留，導致工作減少;當計算逆時，即使你知道用帶狀矩陣近似也是可以的，但仍然會有大量的填充（增加非零值）

把它放在一起我建議你試試出R matrix package爲您的矩陣。嘗試所有可用的簽名並確保安裝了高性能的BLAS實現。也嘗試重寫您的來電計算逆：

# e.g. rewrite... 
A_inverse = solve(A) 
x = y * A_inverse 
# ... as 
x = solve(A, y) 

這可能是你的目的更微妙的，但有一個你應該能夠做到這一點非常高的機會，如包文檔建議：

solve(a, b, ...) ## *the* two-argument version, almost always preferred to 
solve(a)   ## the *rarely* needed one-argument version 

如果一切都失敗了，你可能必須嘗試在提供更有效的實現：Matlab，Suite Sparse，PetSC，Eigen或Intel MKL。