matrix - LU分解N^3

Question

假设我有一个正方形 NXN 对称实数矩阵 A，并且我想计算 A 的 LU 分解。最好的算法来做到这一点

• 如果 A 是稠密矩阵
• 如果 A 是稀疏矩阵？

Answer 1

维基百科声称以下内容：

如果两个 n 阶矩阵可以在时间 M(n) 内相乘，其中对于某些 a>2，M(n)≥na，则可以在时间 O(M(n)) 内计算 LU 分解。这意味着，例如，存在基于 Coppersmith-Winograd 算法的 O(n^2.376) 算法。

对于稀疏矩阵，没有单一的答案。这取决于稀疏性的性质。

Answer 2

我会说稀疏矩阵乘法与密集矩阵乘法的顺序相同，因为（1）这些顺序度量仅适用于数据太大以至于顺序效应占主导地位的情况，以及（2）稀疏性最多会通过与大小为 N，因此随着 N 的增长，但稀疏度保持不变，计算应该再次增加为 O(N^3)。与往常一样，在现实世界中，您的数据大小可能不足以让这方面的性能（顺序）占主导地位，使用缓存和优化内核将更加重要。