在我正在写的一篇论文中,我使用了一个 nxn 矩阵乘以一个维度为 n 的密集向量。在其自然形式中,该矩阵具有 O(n^2) 空间复杂度,并且乘法需要时间 O(n^2)。
但是,众所周知,矩阵是对称的,并且沿其对角线具有零值。该矩阵也是高度稀疏的:大多数非对角元素为零。
任何人都可以将我链接到使用稀疏对称矩阵表示来接近 O(nlogn) 甚至 O(n) 的算法/论文/数据结构,在高度稀疏的情况下?
在我正在写的一篇论文中,我使用了一个 nxn 矩阵乘以一个维度为 n 的密集向量。在其自然形式中,该矩阵具有 O(n^2) 空间复杂度,并且乘法需要时间 O(n^2)。
但是,众所周知,矩阵是对称的,并且沿其对角线具有零值。该矩阵也是高度稀疏的:大多数非对角元素为零。
任何人都可以将我链接到使用稀疏对称矩阵表示来接近 O(nlogn) 甚至 O(n) 的算法/论文/数据结构,在高度稀疏的情况下?
你对这种并行算法感兴趣吗 http://www.cs.cmu.edu/~scandal/cacm/node9.html
我会看一下 Tim Davis 的csparse库。还有一本相应的书描述了一系列稀疏矩阵算法。
在稀疏的情况下,A*x
可以使操作以O(|A|)
复杂的方式运行——即矩阵中非零元素的数量呈线性。