Gig*_*igo 5 math optimization linear-algebra mathematical-optimization adjacency-matrix
我需要将矩阵的迹计算为 3 和 4 的幂，并且它需要尽可能快。
这里的矩阵是一个简单图的邻接矩阵，因此它是正方形的，对称的，它的条目总是 1 或 0，对角线元素总是 0。
对于矩阵的 2 次幂的迹的优化是微不足道的：
我在维基百科上发现的另一个想法是总结 Hadamard 乘积的所有元素，即 entry-wise multiplication，但我不知道如何将这种方法扩展到 3 和 4 的幂。
见http://en.wikipedia.org/wiki/Trace_(linear_algebra)#Properties
也许我只是瞎了，但我想不出一个简单的解决方案。
最后我需要一个 C++ 实现，但我认为这对问题并不重要。
在此先感谢您的帮助。
好吧，我刚刚自己解决了这个问题。我不知道的重要事情是：
如果 A 是有向图或无向图 G 的邻接矩阵，则矩阵 An（即 A 的 n 个副本的矩阵乘积）有一个有趣的解释：行 i 和列 j 中的条目给出了（有向图或无向图）的数量。无向）从顶点 i 到顶点 j 的长度为 n 的行走。例如，这意味着无向图 G 中三角形的数量恰好是 A^3 除以 6 的迹。
（复制自http://en.wikipedia.org/wiki/Adjacency_matrix#Properties）
当处理稀疏图并使用邻接表而不是矩阵时，检索所有 n 个节点从节点 i 到 i 的给定长度的路径数基本上可以在 O(n) 内完成。
尽管如此，还是感谢您的回答！
| 归档时间： |
|
| 查看次数： |
14624 次 |
| 最近记录： |