complexity-theory - 稀疏对称矩阵预乘全向量最低阶复杂度引用

Question

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

但是，已知矩阵是对称的，并且沿其对角线具有零值。该矩阵也是高度稀疏的:大多数非对角元素为零。

任何人都可以将我链接到算法/论文/数据结构，该结构使用稀疏对称矩阵表示来接近 O(nlogn) 甚至 O(n)，在高度稀疏的情况下？

Answer 1

我会看看csparse蒂姆戴维斯的图书馆。还有一本相应的书描述了一系列稀疏矩阵算法。

在稀疏情况下 A*x操作可以在O(|A|)中运行复杂性 - 即矩阵中非零元素的数量呈线性。