稀疏对称矩阵预乘全向量最低阶复杂度参考
在我正在写的一篇论文中，我使用了一个 nxn 矩阵乘以一个维度为 n 的密集向量。在其自然形式下，该矩阵具有 O(n^2) 空间复杂度，并且乘法需要 O(n^2) 时间。
然而，众所周知，该矩阵是对称的，并且沿其对角线具有零值。该矩阵也是高度稀疏的：大多数非对角线项为零。
谁能将我链接到一个算法/论文/数据结构，该结构使用稀疏对称矩阵表示来接近 O(nlogn) 甚至在高稀疏性的情况下 O(n) ？
In a paper I'm writing I make use of an n x n matrix multiplying a dense vector of dimension n. In its natural form, this matrix has O(n^2) space complexity and the multiplication takes time O(n^2).
However, it is known that the matrix is symmetric, and has zero values along its diagonal. The matrix is also highly sparse: the majority of non-diagonal entries are zero.
Could anyone link me to an algorithm/paper/data structure which uses a sparse symmetric matrix representation to approach O(nlogn) or maybe even O(n), in cases of high sparsity?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我想看看 Tim Davis 的 csparse 库。还有一本相应的书描述了一系列稀疏矩阵算法。
在稀疏情况下，
A*x运算可以以O(|A|)复杂度运行 - 即与矩阵中非零元素的数量呈线性关系。I would have a look at the csparse library by Tim Davis. There's also a corresponding book that describes a whole range of sparse matrix algorithms.
In the sparse case the
A*xoperation can be made to run inO(|A|)complexity - i.e. linear in the number of non-zero elements in the matrix.您对此类并行算法感兴趣吗
http://www.cs.cmu.edu/~scandal/cacm/node9 .html
Are you interested in parallel algorithms of this sort
http://www.cs.cmu.edu/~scandal/cacm/node9.html