gpt4 book ai didi

python - 创建和反转大型 Galois 域矩阵

转载 作者:太空宇宙 更新时间:2023-11-04 03:46:10 25 4
gpt4 key购买 nike

我有一个大小为 128x128 的矩阵。每个条目都是一个二进制字段元素(在我的用例中,只有 0 和 1)。我尝试在 matlab 中反转这个矩阵。我在 matlab 中找到了一些可以在此处执行有限域矩阵求逆的函数 http://www.mathworks.com/help/comm/galois-field-computations.html .

但是,这些内置函数仅支持最大 16x16 的矩阵大小。还有其他方法可以克服这个限制吗?我愿意使用其他工具,例如 python 或 C/C++。

如果您想尝试您的方法,这里是测试矩阵及其逆矩阵。

矩阵A[0,0,0,1,0,0,1,0;1,1,1,0,1,0,1,1;1,1,1,0,1,1,0,1;0 ,1,0,0,0,0,1,0;0,1,1,1,1,1,1,0;1,0,1,1,0,0,1,0;0,0 ,1,0,0,0,1,0;0,0,0,0,0,1,0,0]

矩阵 A^-1[1,1,1,0,0,1,1,1;0,1,1,1,0,0,0,1;0,1,1,0,0,0,1,1;1 ,1,1,0,0,0,0,1;1,0,0,1,1,0,1,1;0,0,0,0,0,0,0,1;0,1 ,1,0,0,0,0,1;0,1,0,0,1,1,1,1]

最佳答案

可以通过执行 Gaussian elimination 来实现伽罗华域上的矩阵求逆。 (在 Galois 域中执行所有算术)[A | I],结果是 [I | A^-1].

下面是一些执行高斯消元(行减少)的伪代码。

def row_reduce(A):
A_rre = A.copy()
p = 0 # The pivot

for j in range(A.shape[1]):
# Find a pivot in column `j` at or below row `p`
idxs = np.nonzero(A_rre[p:,j])[0]
if idxs.size == 0:
continue
i = p + idxs[0] # Row with a pivot

# Swap row `p` and `i`. The pivot is now located at row `p`.
A_rre[[p,i],:] = A_rre[[i,p],:]

# Force pivot value to be 1
A_rre[p,:] /= A_rre[p,j]

# Force zeros above and below the pivot
idxs = np.nonzero(A_rre[:,j])[0].tolist()
idxs.remove(p)
A_rre[idxs,:] -= np.multiply.outer(A_rre[idxs,j], A_rre[p,:])

p += 1
if p == A_rre.shape[0]:
break

return A_rre

我有这个用例,但找不到完成此操作的 Python 库。所以我创建了一个 Python 包 galois在 Galois 域上扩展 NumPy 数组。它支持使用普通 np.linalg 函数的线性代数。

这是一个使用您的测试矩阵的示例。

In [1]: import numpy as np                                                                              

In [2]: import galois

In [3]: GF = galois.GF(2)

In [4]: A = GF([[0,0,0,1,0,0,1,0],[1,1,1,0,1,0,1,1],[1,1,1,0,1,1,0,1],[0,1,0,0,0,0,1,0],[0,1,1,1,1,1,1,0
...: ],[1,0,1,1,0,0,1,0],[0,0,1,0,0,0,1,0],[0,0,0,0,0,1,0,0]]); A
Out[4]:
GF([[0, 0, 0, 1, 0, 0, 1, 0],
[1, 1, 1, 0, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1, 0, 1],
[0, 1, 0, 0, 0, 0, 1, 0],
[0, 1, 1, 1, 1, 1, 1, 0],
[1, 0, 1, 1, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 1, 0, 0]], order=2)

In [5]: A_inv = np.linalg.inv(A); A_inv
Out[5]:
GF([[1, 1, 1, 0, 0, 1, 1, 1],
[0, 1, 1, 1, 0, 0, 0, 1],
[0, 1, 1, 0, 0, 0, 1, 1],
[1, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 1, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 1, 1, 1, 1]], order=2)

In [6]: A @ A_inv
Out[6]:
GF([[1, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1]], order=2)

关于python - 创建和反转大型 Galois 域矩阵,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24248380/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com