稀疏对称矩阵预乘全向量最低阶复杂度参考

Question

在我正在写的一篇论文中，我使用了一个 nxn 矩阵乘以一个维度为 n 的密集向量。在其自然形式下，该矩阵具有 O(n^2) 空间复杂度，并且乘法需要 O(n^2) 时间。

然而，众所周知，该矩阵是对称的，并且沿其对角线具有零值。该矩阵也是高度稀疏的：大多数非对角线项为零。

谁能将我链接到一个算法/论文/数据结构，该结构使用稀疏对称矩阵表示来接近 O(nlogn) 甚至在高稀疏性的情况下 O(n) ？

Answer 1

我想看看Tim Davis 的csparse库。还有一本相应的书描述了一系列稀疏矩阵算法。

在稀疏情况下，A*x可以使运算以O(|A|)复杂度运行——即与矩阵中非零元素的数量成线性。