Większy obraz wyboru matryc w algorytmie Strassena

17

W algorytmie Strassena, aby obliczyć iloczyn dwóch macierzy $\mathbf{A}$ i , macierze i są podzielone na macierze blokowe i algorytm kontynuuje rekurencyjne obliczanie bloków produkty matryca-matryca w przeciwieństwie do naiwnych blokowych produktów matrycowo-matrycowych, tj. jeśli chcemy , gdzie $\mathbf{B}$ $\mathbf{A}$ $\mathbf{B}$ $2 \times 2$ $7$ $8$ $\mathbf{C}=\mathbf{A} \mathbf{B}$

ZA = [\begin{matrix} {ZA}_{1, 1} & {ZA}_{1, 2)} \\ {ZA}_{2), 1} & {ZA}_{2), 2)} \end{matrix}], b = [\begin{matrix} b_{1, 1} & b_{1, 2)} \\ b_{2), 1} & b_{2), 2)} \end{matrix}], do = [\begin{matrix} {do}_{1, 1} & {do}_{1, 2)} \\ {do}_{2), 1} & {do}_{2), 2)} \end{matrix}]

$\mathbf{A} =\begin{bmatrix} \mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\ \mathbf{A}_{2,1} & \mathbf{A}_{2,2} \end{bmatrix} \mbox { , } \mathbf{B} = \begin{bmatrix} \mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\ \mathbf{B}_{2,1} & \mathbf{B}_{2,2} \end{bmatrix} \mbox { , } \mathbf{C} = \begin{bmatrix} \mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\ \mathbf{C}_{2,1} & \mathbf{C}_{2,2} \end{bmatrix}$ mamy więc który wymaga

{do}_{1, 1} = {ZA}_{1, 1} b_{1, 1} + {ZA}_{1, 2)} b_{2), 1} {do}_{1, 2)} = {ZA}_{1, 1} b_{1, 2)} + {ZA}_{1, 2)} b_{2), 2)} {do}_{2), 1} = {ZA}_{2), 1} b_{1, 1} + {ZA}_{2), 2)} b_{2), 1} {do}_{2), 2)} = {ZA}_{2), 1} b_{1, 2)} + {ZA}_{2), 2)} b_{2), 2)}

$\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}\\ \mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}\\ \mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}\\ \mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2}$

8

$8$ mnożenia. Zamiast tego w Strassen obliczamy i uzyskaj używa jako as

{M.}_{1} : = ({ZA}_{1, 1} + {ZA}_{2), 2)}) (b_{1, 1} + b_{2), 2)}) {M.}_{2)} : = ({ZA}_{2), 1} + {ZA}_{2), 2)}) b_{1, 1} {M.}_{3)} : = {ZA}_{1, 1} (b_{1, 2)} - b_{2), 2)}) {M.}_{4} : = {ZA}_{2), 2)} (b_{2), 1} - b_{1, 1}) {M.}_{5} : = ({ZA}_{1, 1} + {ZA}_{1, 2)}) b_{2), 2)} {M.}_{6} : = ({ZA}_{2), 1} - {ZA}_{1, 1}) (b_{1, 1} + b_{1, 2)}) {M.}_{7} : = ({ZA}_{1, 2)} - {ZA}_{2), 2)}) (b_{2), 1} + b_{2), 2)})

$\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})\\ \mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}\\ \mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})\\ \mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})\\ \mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}\\ \mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})\\ \mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})$

C_{i, j}

$\mathbf{C}_{i,j}$

M_{k}

$\mathbf{M}_{k}$

{do}_{1, 1} = {M.}_{1} + {M.}_{4} - {M.}_{5} + {M.}_{7} {do}_{1, 2)} = {M.}_{3)} + {M.}_{5} {do}_{2), 1} = {M.}_{2)} + {M.}_{4} {do}_{2), 2)} = {M.}_{1} - {M.}_{2)} + {M.}_{3)} + {M.}_{6}

$\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}\\ \mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}\\ \mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}\\ \mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}$ Jednak wybór macierzy wydaje mi się arbitralny. Czy istnieje szerszy obraz tego, dlaczego wybieramy te konkretne produkty z macierzy i

? Spodziewałbym się także, że

będzie angażował

i

w symetryczny sposób, co nie wydaje się, że tak właśnie jest. Na przykład mamy

M_{k}

$\mathbf{M}_k$

A

$\mathbf{A}$

B

$\mathbf{B}$

M_{k}

$\mathbf{M}_k$

A_{i, j}

$\mathbf{A}_{i,j}$

B_{i, j}

$\mathbf{B}_{i,j}$

M_{2} := (A_{2, 1} + A_{2, 2}) B_{1, 1}

$\mathbf{M}_2: = (\mathbf{A}_{2,1}+\mathbf{A}_{2,2})\mathbf{B}_{1,1}$ . Spodziewałbym się, że jego odpowiednik powie, że również zostanie obliczony. Jednak nie jest tak, ponieważ można go uzyskać z innych .

A_{1, 1} (B_{1, 2} + B_{2, 2})

$\mathbf{A}_{1,1} (\mathbf{B}_{1,2} + \mathbf{B}_{2,2})$

M_{k}

$\mathbf{M}_k$

Byłbym wdzięczny, gdyby ktoś mógł rzucić na to trochę światła.

ds.algorithms linear-algebra matrices matrix-product Społeczność
źródło

15

De Groote (O odmianach optymalnych algorytmów obliczania odwzorowań dwuliniowych. II. Optymalne algorytmy mnożenia macierzy 2x2. Teoria. Obliczanie. Sci. 7: 127-148, 1978) dowodzi, że istnieje tylko jeden algorytm do pomnożenia -macierze z 7 mnożeniami aż do równoważności. Może to być unikalna funkcja mnożenia . (Uwaga: W literaturze znajdziesz różne warianty algorytmu Strassena. Wszystkie są równoważne z właściwym pojęciem równoważności.) $2 \times 2$ $2 \times 2$

Jeśli zaczniesz teraz wykazywać dolną granicę dla mnożenia macierzy - zobacz, jak to zrobić w książce Bürgissera, Clausena i Shokrollahi - algorytm Strassena lub jakiś wariant pokazuje się całkiem naturalnie. Dowiesz się wielu tożsamości, które określają wygląd produktów. Następnie możesz zakończyć zgadywanie. (Dowód De Groote pokazuje, że nawet zgadywanie nie jest konieczne.) $2 \times 2$

Schönhage powiedział mi kiedyś, że Strassen powiedział mu kiedyś, że znalazł swój algorytm w ten sposób, próbując udowodnić dolną granicę.

Markus Bläser
źródło

11

$A_0,A_1,A_2,A_3$ $B_0,B_1,B_2,B_3$ $2\times 2$ $A_iB_j \in \{0,A_0,A_1,A_2,A_3,B_0,B_1,B_2,B_3\}$ $A_0 = B_0$ $A$ $B$ $A_0=B_0,A_1,A_2,A_3,B_1,B_2,B_3$ $M$

Nie wiem, czy Strassen wymyślił taki sposób patrzenia na to. Biorąc pod uwagę inne tożsamości leżące u podstaw algorytmów szybkiego mnożenia macierzy, nie jest jasne, czy dzieje się coś głębszego, niż jakaś wypracowana formuła. Przeszliśmy już to wcześniej - Lagrange wykorzystał tożsamość czterech kwadratów (która była znana wcześniej), aby udowodnić twierdzenie o czterech kwadratach. Na początku musiała to być osobliwa tożsamość algebraiczna, ale teraz wiemy, że określa ona właściwość multiplikatywności normy czwartorzędowej. Biorąc pod uwagę obecny stan wiedzy, trudno powiedzieć, czy powyższa interpretacja jest tak produktywna.

Yuval Filmus
źródło

3

2 \times 2

$2\times 2$

Większy obraz wyboru matryc w algorytmie Strassena

Odpowiedzi: