Использование индекса вместо нарезки в алгоритме Штрассена - PullRequest
Новая
       17

Использование индекса вместо нарезки в алгоритме Штрассена

0 голосов
/ 27 февраля 2020

Я реализую алгоритм Штрассена для умножения матриц, используя метод нарезки 

def decoupM(M):
    A = M[:len(M)/2,:len(M)/2]
    B = M[:len(M)/2,len(M)/2:]
    C = M[len(M)/2:,:len(M)/2]
    D = M[len(M)/2:,len(M)/2:]
    return A,B,C,D


def multi(M,N):
    m = len(M[0])
    if m == 1:
        return M*N

    A,B,C,D = decoupM(M)
    E,F,G,H = decoupM(N)

    P1 = multi(A,F-H)
    P2 = multi(A+B,H)
    P3 = multi(C+D,E)
    P4 = multi(D,G-E)
    P5 = multi(A+D,E+H)
    P6 = multi(B-D,G+H)
    P7 = multi(A-C,E+F)

    MN11 = -P2+P4+P5+P6
    MN12 = P1+P2
    MN21 = P3+P4
    MN22 = P1-P3+P5-P7

    Z = np.zeros((m,m))
    Z[:m/2,:m/2] = MN11
    Z[:m/2,m/2:] = MN12
    Z[m/2:,:m/2] = MN21
    Z[m/2:,m/2:] = MN22

    return Z

Он работает нормально, мне нужно избегать сложностей с использованием индекса, это предложение не работает 

## implementation using  index
def MultMat(M,N):

    Z = np.zeros((len(M),len(M)))
    multiOpt(M,N,len(M),len(M)*2,Z)
    return Z


def multiOpt(M,N,i,j,Z):
    if j-i == 1:
        Z[i:j][i:j] = M[i:j][i:j]*N[i:j][i:j]
        return Z

# +++++++++
# + A + B + A is M[:i/2][:i/2]  B is M[:i/2][i/2:] 
# +++++++++
# + C + D + C is M[i/2:][:i/2]  D is M[i/2:][i/2:] 
# +++++++++

# +++++++++
# + E + F + E is N[:i/2][:i/2]  F is N[:i/2][i/2:]
# +++++++++
# + G + H + G is N[:i/2][:i/2]  H is N[:i/2][i/2:]
# +++++++++

    P1 = multiOpt(M[0:i/2][0:i/2],N[:i/2][i/2:]-N[:i/2][i/2:],i/2,j/2,Z)
    P2 = multiOpt(M[:i/2][:i/2]+M[:i/2][i/2:],N[:i/2][i/2:],i/2,j/2,Z)
    P3 = multiOpt(M[i/2:][:i/2]+M[i/2:][i/2:] ,N[:i/2][:i/2],i/2,j/2,Z)
    P4 = multiOpt(M[i/2:][i/2:] ,N[:i/2][:i/2]-N[:i/2][:i/2],i/2,j/2,Z)
    P5 = multiOpt(M[:i/2][:i/2]+M[i/2:][i/2:] ,N[:i/2][:i/2]+N[:i/2][i/2:],i/2,j/2,Z)
    P6 = multiOpt(M[:i/2][i/2:]-M[i/2:][i/2:] ,N[:i/2][:i/2]+N[:i/2][i/2:],i/2,j/2,Z)
    P7 = multiOpt(M[:i/2][:i/2]-M[i/2:][:i/2],N[:i/2][:i/2]+N[:i/2][i/2:],i/2,j/2,Z)

    Z[:i/2][:i/2] = -P2+P4+P5+P6
    Z[:i/2][i/2:] = P1+P2
    Z[i/2:][:i/2] = P3+P4
    Z[i/2:][i/2:] = P1-P3+P5-P7

    return Z

Подробнее о Алгоритм Штрассена : В линейной алгебре алгоритм Штрассена, названный в честь Фолькера Штрассена, является алгоритмом умножения матриц. Он быстрее стандартного алгоритма умножения матриц и полезен на практике для больших матриц, но будет медленнее, чем самые быстрые известные алгоритмы для чрезвычайно больших матриц.

Алгоритм Штрассена работает для любого кольца, например, плюс / умножение , но не все полукольца, такие как min-plus или булева алгебра, где наивный алгоритм все еще работает, и так называемое комбинаторное матричное умножение.

...