matrix - 使用特征值求解稀疏矩阵

Question

我正在编写基于 this 的基于约束的粒子系统纸。约束 C 的雅可比矩阵与系统中的粒子数和约束数成比例。因为每个约束通常只有几个依赖于它的粒子，所以矩阵会非常稀疏。我认为在 Eigen 中使用稀疏矩阵来求解系统可能会有所帮助。根据 Eigen reference material ，似乎有几种不同的方法可以求解这些稀疏矩阵方程。我的问题是:

1. 这些矩阵的大小首先需要使用稀疏矩阵吗？我需要存储雅可比矩阵及其时间导数。每个都是一个 Mx3N 矩阵，其中 M 是约束的数量，N 是粒子的数量。我的粒子系统的用户大概可以在合理范围内添加任意数量的粒子。
2. 关于稀疏矩阵表示在密集矩阵上的争论更多的是关于性能或内存消耗。稀疏矩阵的求解速度能否比稠密矩阵快？这取决于什么？
3. 我对这些求解器的实现了解不多。我没有对这些算法进行太多研究，尤其是在稀疏矩阵方程的背景下。这些算法的性能如何，我应该选择哪一个？我记得几年前在我的线性代数课上学习过其中的一些，我相信其中很多是 O(n^3)，这对于本文描述的系统来说似乎不太适用。

Answer 1

如果 N 小于 1000，那么您可能会使用密集存储，否则最好使用稀疏表示。每行非零的数量应该非常小，比如 10 个左右，但不超过 100 个，以保持求解器的效率。稀疏求解器的复杂性实际上小于 O(N*K)，其中 K 是非零值的数量。因此，对于非常稀疏的矩阵，它们可以比密集求解器快几个数量级。