Блог

Главная - Вопросы по программированию - Быстрое точечное умножение разреженной матрицы в GF (256) с помощью Scipy.Разреженный

Быстрое точечное умножение разреженной матрицы в GF (256) с помощью Scipy.Разреженный

#python #performance #scipy #sparse-matrix #galois-field

#python #Производительность #scipy #разреженная матрица #галуа-поле

Вопрос:

Мне нужно увеличить скорость моего алгоритма. Метод принимает две матрицы в качестве аргумента и выполняет точечное умножение. Единственная проблема заключается в том, что элементы должны быть умножены как октеты в GF (256), а затем добавлены как XOR. Поскольку я имею дело с очень большими разреженными матрицами, производительность ужасна.

 def matrix_oct_mult(U, V, OCT_EXP, OCT_LOG):
temp_sum = 0
if shape(U)[1] == None and shape(V)[1] == None:
    for i in range(len(U)):
        temp_sum = oct_sum(temp_sum, oct_mult(U[i], V[i], OCT_EXP, OCT_LOG))
    return temp_sum
assert shape(U)[1] == shape(V)[0], "Wrong size requirements for matrix dot multiplication"
temp_sum = 0
W = sp.lil_matrix((shape(U)[0], shape(V)[1]))
for i in range (shape(U)[0]):
    for z in range(shape(V)[1]):
        for j in range (shape(U)[1]):
             temp_sum = oct_sum(temp_sum, oct_mult(U[i, j], V[j, z], OCT_EXP, OCT_LOG))

        W[i, z] = temp_sum
        temp_sum = 0
return W

Как вы можете видеть, я пробовал с классом lil, но производительность по-прежнему низкая.

Есть ли какие-либо эффективные способы решения этой проблемы?

Комментарии:

1. Python не является компилируемым языком, и вложенные циклы для операций с матрицами всегда будут исключительно медленными. Вам следует реструктурировать свою проблему для работы со стандартными матричными операциями или написать это на скомпилированном языке по вашему выбору.

2. Я не понимаю, где вы используете преимущество разреженности U или V или результата W . Для такой итерации было бы лучше использовать обычный ndarray (или даже списки списков). Даже с lil доступом к элементу разреженной матрицы происходит медленно.

Ответ №1:

Поскольку Python интерпретируется, вложенные for циклы, как известно, имеют низкую производительность. Тогда как эквивалентные for циклы в C были бы быстрыми. Таким образом, наилучшая производительность достигается при скомпилированном коде.

По этой причине я написал библиотеку Python под названием galois, которая расширяет массивы NumPy для работы с полями Галуа. Я написал код на Python, но JIT скомпилировал его с использованием Numba, поэтому арифметика поля Галуа работает так же быстро или почти так же быстро, как и арифметика собственного массива NumPy, см. Это Сравнение производительности .

Библиотека поддерживает линейную алгебру на матрицах полей Галуа с использованием стандартных двоичных операторов ( , @ , etc) и обычных функций линейной алгебры NumPy. Большинство этих подпрограмм также скомпилированы JIT для ускорения.

Я полагаю, что вы пытаетесь выполнить матричное умножение на две матрицы ( (M,N) x (N,K) ). Вот пример, в galois котором это делается.

 In [1]: import galois                                                                                                                                                                          

# Create the GF(2^8) field using AES's irreducible polynomial -- your's may be different
In [2]: GF = galois.GF(2**8, irreducible_poly=0x11b)                                                                                                                                           

In [3]: print(GF.properties)                                                                                                                                                                   
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: x^8   x^4   x^3   x   1
  is_primitive_poly: False
  primitive_element: x   1

In [4]: A = GF.Random((3,4)); A                                                                                                                                                                
Out[4]: 
GF([[ 35, 130, 167, 111],
    [ 58, 161, 194, 200],
    [244,  65, 160,   8]], order=2^8)

In [5]: B = GF.Random((4,5)); B                                                                                                                                                                
Out[5]: 
GF([[ 50,  59,  23,  34,  38],
    [ 16,  59, 162,  80, 250],
    [205, 145, 114,   9,  40],
    [212, 250, 162, 210,  72]], order=2^8)

In [6]: A @ B                                                                                                                                                                                  
Out[6]: 
GF([[144, 236, 142,  90,  89],
    [ 83, 171,  34,   2, 117],
    [192,   1,  20, 208, 127]], order=2^8)