GF4域矩阵乘法耗时过长，求基于numpy与galois库的优化方法

问题描述 #

使用np.dot计算GF(4)域矩阵乘法时，r≤6时速度正常，但r=7时耗时剧增。采用galois库结合numpy实现，自行实现GF(4)运算后用numpy做矩阵乘法耗时更长。r=7时矩阵规模为5454×5454与5454×5461，并非超大规模但性能骤降。

原代码片段 #

import numpy as np
import galois


def family_Hamming(q,r):
    n = int((q**r-1)/(q-1))
    k = int((q**r-1)/(q-1)-r)
    res = (n,k)
    return res

q = 4
r = 7

n,k = family_Hamming(q,r)

GF = galois.GF(2**2)

# (5454, 5454)
a = GF(np.random.randint(4, size=(k, k)))
# (5454, 5461)
b = GF(np.random.randint(4, size=(k, n)))
c = np.dot(a,b)
print(c)

优化方案 #

• 切换galois的运算模式为JIT编译：默认情况下galois.GF可能使用未优化的后端，指定mode="jit"利用numba即时编译GF运算，大幅提升大矩阵计算速度：

  GF = galois.GF(2**2, mode="jit")
  

• 改用galois重载的@运算符替代np.dot：np.dot未针对galois.GF数组做特殊优化，而@是galois专门实现的矩阵乘法，适配GF域运算逻辑，性能更优：

  c = a @ b
  

• 使用galois原生随机矩阵生成：避免先生成numpy整数数组再转换为GF数组的额外开销，直接用GF.Random()生成矩阵：

  a = GF.Random((k, k))
  b = GF.Random((k, n))
  

• 开启多线程加速：galois的JIT模式依赖numba，可设置numba使用多核CPU提升并行计算效率：

  import numba
  numba.set_num_threads(8)  # 根据自身CPU核心数调整
  

内容的提问来源于stack exchange，提问作者Дима Бобрикович