我想找到一个大矩阵的一个简化的行梯队形式(在F_q字段中)。 我尝试了以下代码。 虽然我使用gmpy2库来加速,但程序仍然内存不足。因为我的输入矩阵非常大(100x2^15),p也非常大(| p |=256位)。有人能建议如何降低这个alg的复杂性吗。在
谢谢
def invmodp(a, p):
return gmpy2.invert(a,p)
def division_mod(a, b, p): #a/b mod p
invert = invmodp(b, p)
return (a * invert) %p
def row_echelon_form(M, p):
lead = 0
rowCount = len(M)
columnCount = len(M[0])
for r in range(rowCount):
if lead >= columnCount:
return
i = r
while M[i][lead] == 0:
i += 1
if i == rowCount:
i = r
lead += 1
if columnCount == lead:
return
M[i],M[r] = M[r],M[i]
lv = M[r][lead]
M[r] = [ division_mod(mrx, lv, p) for mrx in M[r]]
for i in range(rowCount):
if i != r:
lv = M[i][lead]
M[i] = [ (iv - lv*rv)%p for rv,iv in zip(M[r],M[i])]
lead += 1
return M
通过使用
gmpy2.divm
替换您的division_mod
,我可以节省几秒钟的运行时间。我无法做出任何其他重大的改进。下面的程序创建一个随机的100×2^15矩阵,并在大约3分钟内计算出行梯队形式,并消耗425MB内存。在如果您的内存使用量增长超过大约500MB,则您的
gmpy2
版本中可能存在内存泄漏。或者我错误地解释了您的需求,而矩阵明显更大。在免责声明:我维护
gmpy2
。在相关问题 更多 >
编程相关推荐