Quadro maior por trás da escolha de matrizes no algoritmo de Strassen

No algoritmo Strassen, para calcular o produto de duas matrizes e B , as matrizes A e B estão divididos em 2 × 2 matrizes de blocos e o algoritmo procede de forma recursiva computação 7 bloco produtos matriz-matriz, por oposição a um naive 8 matriz-bloco produtos matriciais, ou seja, se queremos C = A B , onde A = [ A 1 , 1 A 1 , 2 A 2 , 1 A 2 , $\mathbf{A}$$\mathbf{B}$$\mathbf{A}$$\mathbf{B}$$2 \times 2$$7$$8$$\mathbf{C}=\mathbf{A} \mathbf{B}$ então temos C 1 , 1 = A 1 , 1 B 1 , 1 + A

$$\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}$$ que requer8multiplicações. Em vez disso, em Strassen, calculamos M 1 :=( A 1 , 1 + A 2 , 2 )( B 1 , 1 + 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$ e obtenha C i , j usando M k 's como C 1 , 1 = M 1 + M 4 - M 5 + M $$\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})$$ $\mathbf{C}_{i,j}$$\mathbf{M}_{k}$ No entanto, a escolha das matrizes M k 's me parece arbitrária. Existe uma imagem maior do motivo pelo qual escolhemos esses produtos específicos das sub-matrizes de A e B ? Além disso, eu esperaria M k 's para envolver A i , j ' s e B i , j é de uma forma simétrica, o que não parece ser o caso aqui. Por exemplo, temos M 2 : $$\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}$$ $\mathbf{M}_k$$\mathbf{A}$$\mathbf{B}$$\mathbf{M}_k$$\mathbf{A}_{i,j}$$\mathbf{B}_{i,j}$ . Eu esperaria que sua contraparte diga A 1 , 1 ( B 1 , 2 + B 2 , 2 ) também seja computada. No entanto, isso não é uma vez que pode ser obtido a partir de outros M k 's.$\mathbf{M}_2: = (\mathbf{A}_{2,1}+\mathbf{A}_{2,2})\mathbf{B}_{1,1}$$\mathbf{A}_{1,1} (\mathbf{B}_{1,2} + \mathbf{B}_{2,2})$$\mathbf{M}_k$

Eu apreciaria se alguém pudesse lançar alguma luz sobre isso.

$2 \times 2$$2 \times 2$

$2 \times 2$

Schönhage me disse uma vez que Strassen uma vez disse a ele que encontrou seu algoritmo dessa maneira, tentando provar um limite inferior.

$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$

Não sei se Strassen teve essa maneira de encarar. Considerando outras identidades subjacentes aos algoritmos de multiplicação rápida de matriz, não está claro se há algo profundo acontecendo, sob alguma fórmula elaborada. Já falamos sobre isso antes - Lagrange usou a identidade de quatro quadrados (que era conhecida antes) para provar o teorema dos quatro quadrados. A princípio, deve ter sido apenas uma identidade algébrica curiosa, mas agora sabemos que afirma a propriedade de multiplicatividade da norma de quaternião. Dado o estado atual do conhecimento, é difícil dizer se a interpretação acima é tão produtiva.