有效地解決稀疏矩陣

Question

爲了解決備用矩陣，

在一般情況下，有多大確實矩陣必須是（作爲一個經驗法則）

像congraduate下降法比蠻力解決者快（那不利用稀疏性）？

Answer 1

我不確定共軛梯度求解器和'蠻力'求解器之間的二分法是否有用。例如，CG可以應用於密集矩陣和稀疏矩陣。你可能會發現this book有幫助。

Answer 2

它不僅取決於矩陣的大小，還取決於它們的稀疏程度以及它們具有的稀疏結構。很明顯，你可以比一個具有相同數量的非零條目的系統快速地解決一個三對角線系統的問題。

正如高性能馬克指出的那樣，CG適用於稠密矩陣以及稀疏矩陣，所以您想要問的問題更多的是「在求解器之前矩陣需要多大以及稀疏程度如何」受益於將其視爲稀疏矩陣而不是恰好具有很多零的稠密矩陣「。

正如我所指出的，對此的回答取決於稀疏結構。作爲第一次猜測，沒有特殊結構的矩陣是10％滿的，我將使用密集方法，直到矩陣填充高速緩存（在現代商品硬件上，這將約爲1000 x 1000）。如果矩陣顯着更稀疏，或者有一些特殊的結構可以更容易地處理（例如，非零數據密集塊或某些頻帶結構），那麼該閾值將變得更小。

你能給我們提供關於你正在使用的具體問題的更多信息嗎？