高效求解稀疏矩阵
对于求解备用矩阵，
一般来说，矩阵必须有多大（根据经验）
才能使聚合下降等方法比蛮力求解器（不利用稀疏性）更快？
For solving spare matrices,
in general, how big does the matrix have to be (as a rule of thumb)
for methods like congraduate descent to be faster than brute force solvers (that do not take advantage o sparsity)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
它不仅取决于矩阵的大小，还取决于它们的稀疏程度以及它们具有什么稀疏结构。显然，解决三对角系统的速度比解决矩阵中随机分布的相同数量非零项的系统快得多。
正如 High-Performance Mark 所指出的，CG 既适用于密集矩阵，也适用于稀疏矩阵，因此您想问的问题更多的是“矩阵需要有多大和有多稀疏，求解器才能受益于 将其视为稀疏矩阵，而不是恰好有很多零的密集矩阵”。
正如我所指出的，这个问题的答案取决于稀疏结构。一个没有特殊结构且已满 10% 的矩阵，作为第一个猜测，我会使用密集方法，直到矩阵填充缓存（在现代商用硬件上，这将约为 1000 x 1000）。如果矩阵非常稀疏，或者具有某种使其更易于使用的特殊结构（例如，密集的非零数据块或某种能带结构），则该阈值将变得小得多。
您能否向我们提供有关您正在处理的具体问题的更多信息？
It depends not only on the size of the matrices, but also how sparse they are, and what sparseness structure they have. Obviously, you can solve a tridiagonal system much faster than a system with the same number of non-zero entries distributed randomly through the matrix.
As High-Performance Mark noted, CG works for dense matrices as well as sparse, so the question you want to ask is something more along the lines of "how large and how sparse does a matrix need to be before solvers can benefit from treating it as a sparse matrix instead of a dense matrix that happens to have a lot of zeros".
The answer to this depends, as I noted, on the sparseness structure. A matrix with no special structure that's 10% full, as a first guess, I would use dense methods until the matrix filled cache (on modern commodity hardware, that's going to be around 1000 x 1000). If the matrix is dramatically sparser, or has some special structure that makes it easier to work with (dense blocks of non-zero data, or some band structure, for example), then that threshold will become much smaller.
Can you give us more information about the specific problem that you're working with?
我不确定共轭梯度求解器和“强力”求解器之间的二分法是否有用。例如，CG 可以应用于稠密矩阵和稀疏矩阵。您可能会发现这本书很有帮助。
I'm not sure that your dichotomy between conjugate gradient solvers and 'brute force' solvers is useful. CG, for instance, can be applied to both dense and sparse matrices. You might find this book helpful.