计算永久物64 × 6464×64矩阵

计算科学 线性代数 矩阵
2021-12-11 23:35:53

我需要计算几个零一矩阵的Matrix Permanents 。我曾尝试在 Sage 和 Maple 中使用内置函数,但两个程序都返回内存不足错误。我也尝试了几种 MatLab 实现,但它们往往运行得非常缓慢,大约需要几天或几周。64×64

我想知道是否有人对我如何计算这些矩阵永久物有任何建议(函数、程序、方法)。我可以使用 Sage、Maple 和 MatLab,并且我还在 Python 中做了大量的工作。矩阵本身在最密集的情况下每行/列有 16-24 个,在最稀疏的情况下每行/列有 6-8 个。

2个回答

您链接到的维基百科文章有几个参考计算未加权图的永久值,这正是您的情况。探索这些方向可能是值得的。

一般来说,看永久的定义,困难在于64个索引有很多排列——64!事实上,一个相当笨重的数字,大约如果我们暂时忽略这个事实,计算每个排列的权重对于 Matlab/Sage/Maple/... 如果您将矩阵存储为浮点数可能很困难,但如果您编写这样的代码,它应该相当简单在 C/C++ 中并将 0/1 条目存储为布尔值。然后,只要因子为“真”,您只需要计算每个权重的乘积,如果您遇到“假”,则终止计算,继续下一个排列。这类似于分支定界算法。1089

但这并不能解决有这么多排列的问题。我能看到的唯一方法是(i)使用矩阵中的对称性和其他关于矩阵的知识来将“有趣”排列的数量减少到更易于管理的大小,以及(ii)跟进与图表的连接,在特别是 0/1 矩阵的永久值等于循环覆盖的数量。我不是图形专家,但可能有专门的算法来计算周期覆盖。

计算 prmanents 是一个 NP-hard 问题(更清晰的版本,请参见 http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete),因此(除非 P=NP)没有快速的通用算法。这解释了为什么您会耗尽资源。

你需要永久物做什么?也许人们可以重新构造潜在的问题,以使用计算上更适合的东西而不是永久物!