如何避免大元素计算矩阵行列式溢出

Question

我将计算 Python 中随机二维矩阵 (G) 的行列式。该矩阵的大小约为 30 x 30，其中每个元素都是使用 random.randrange(0,P)（例如 P= 2^160 - 47）从具有特征 P 的大质数域中随机选择的。问题是，当我同时使用 scipy 和 numpy 的 det 命令时，它们 return inf。求行列式后想求素数域的答案，即 det(G)% P.

有什么方法可以计算吗？提前谢谢你。

这是一个示例代码：

import numpy as np
import random
from scipy.linalg import det
N= 30
p = 2**160 - 47
G = np.zeros((N, N))
    
for i in range(N):
   for j in range(N):
      G[i][j] = random.randrange(0, p)

ans = det(G)%p

Answer 1

NumPy 不是执行此操作的正确工具。您需要一个可以处理任意大整数的库。一种选择是 SymPy. SymPy even has the function randMatrix 可以生成随机矩阵。例如，

import random
from sympy import randMatrix


N = 30
p = 2**160 - 47

G = randMatrix(N, min=0, max=p-1)

ans = G.det() % p
print(ans)

一个典型的运行打印

381271413373650154061019607002336594108159531272

在 randMatrix 的调用中，我使用了 max=p-1，因为 randMatrix 的文档字符串暗示函数 random.Random.randint 将用于生成随机条目矩阵，并且该函数在可能的随机值中包含 max。 randrange 不包括 max.

如何避免大元素计算矩阵行列式溢出

How to avoid overflow in calculation matrix determinant with large elements

python

numpy

overflow

scipy