Неверная выходная матрица с использованием алгоритма Штрассена с пустыми матрицами

Я пытаюсь реализовать алгоритм умножения матриц Штрассена, как описано в CLRS, с использованием матриц Python 3 и numpy.

Проблема в том, что выходная матрица C возвращается как нулевая матрица вместо правильного продукта. Я не уверен, почему моя реализация не работает, но подозреваю, что это как-то связано с созданием матрицы C при каждом рекурсивном вызове. Я был бы признателен за любое объяснение того, что я делаю неправильно и как я могу это исправить.

Благодарю вас!

import numpy as np

def strassen(A,B):
    n = A.shape[0]
    C = np.zeros((n*n), dtype=np.int).reshape(n,n)
    if n == 1:
        C[0][0] = A[0][0] * B[0][0]

    else:
        k = int(n/2) 

        A11,A21,A12,A22 = A[:k,:k], A[k:, :k], A[:k, k:], A[k:, k:]
        B11,B21,B12,B22 = B[:k,:k], B[k:, :k], B[:k, k:], B[k:, k:]
        C11,C21,C12,C22 = C[:k,:k], C[k:, :k], C[:k, k:], C[k:, k:]

        S1 = B12 - B22
        S2 = A11 + A12
        S3 = A21 + A22
        S4 = B21 - B11
        S5 = A11 + A22
        S6 = B11 + B22
        S7 = A12 - A22
        S8 = B21 + B22
        S9 = A11 - A21
        S10= B11 + B12

        P1 = strassen(A11, S1)
        P2 = strassen(S2, B22)
        P3 = strassen(S3, B11)
        P4 = strassen(A22, S4)
        P5 = strassen(S5, S6)
        P6 = strassen(S7, S8)
        P7 = strassen(S9, S10)

        C11 = P5 + P4 - P2 + P6
        C12 = P1 + P2
        C21 = P3 + P4
        C22 = P5 + P1 - P3 - P7


    return C

python numpy recursion matrix-multiplication strassen
person Community    schedule 05.11.2017    source источник
comment
Ну, вы никогда не изменяете martix C после его создания в строке C = np.zeros((n*n), dtype=np.int).reshape(n,n)   -  person Vladimir Shevyakov    schedule 05.11.2017
comment
Разве кусочки C не ссылаются на оригинал? У меня сложилось впечатление, что пустые слайсы — это просмотры. Как изменить исходную матрицу?   -  person    schedule 05.11.2017
comment
удалите C11,C21,C12,C22 = C[:k,:k] ..., замените C11 = P5 + P4 - P2 + P6 на C[:k,:k] = P5 + P4 - P2 + P6 и сделайте то же самое для следующих строк   -  person gboffi    schedule 05.11.2017
comment
да спасибо я так и сделал   -  person    schedule 05.11.2017
comment
C11 это просто имя. Во-первых, вы используете его, чтобы назвать срез C, во-вторых, вы используете его, чтобы назвать результат выражения. Это как оболочка, 1) ln A C 2) ln -f B C — вы думаете, что файл A теперь содержит содержимое файла B?   -  person gboffi    schedule 06.11.2017
comment
Понятно, я перезаписал переменную при присвоении ей выражения P?   -  person    schedule 06.11.2017
comment
Python не имеет переменных в смысле C, у него есть объекты, созданные при вычислении выражения. Вы можете дать ему имя, много имен, ни одного имени. Если объект является изменяемым (google "изменяемые неизменяемые объекты Python"), вы изменяете его, используя индексирующие (a[3]=0) фрагменты (P[:k,:k]=...) или точку (a=MyClass(); a.xy=(2,4)). Много раз вы оцениваете выражение для его побочных эффектов и не называете имя созданного объекта, например, plt.plot(x,y) возвращает сложную структуру данных, которую вы обычно отбрасываете, потому что вам нужен просто график, отображаемый на экране.   -  person gboffi    schedule 06.11.2017
comment
Ладно, думаю, теперь я понял. спасибо!   -  person    schedule 06.11.2017

Ответы (1)


arrow_upward
2
arrow_downward

ОК, я заставил его работать, просто обновив срезы C[:k,:k] новыми значениями вместо создания новых переменных C11, C12 ..ect. поскольку при этом создается новая матрица, а не ссылка на исходную матрицу C.

person Community    schedule 05.11.2017