Большая картина выбора матриц в алгоритме Штрассена

В алгоритме Штрассена, чтобы вычислить произведение двух матриц и B , матрицы A и B делятся на блочные матрицы 2 × 2, и алгоритм продолжает рекурсивное вычисление 7- блочных матрично-матричных произведений, а не наивных 8- блочных матричных матриц. матричные произведения, т. е. если мы хотим C = A B , где 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}$ тогда мы имеем 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}$$ что требует8умножений. Вместо этого в Штрассене мы вычисляем 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$ и получить C i , j , используя M k в качестве C 1 , 1 = M 1 + M 4 - М 5 + М $$\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}$ Однако выбор матриц M k мне кажется произвольным. Есть ли общая картина, почему мы выбираем эти конкретные произведения подматриц A и B ? Кроме того, я ожидал бы, что M k будет задействовать A i , j и B i , j симметрично, что, похоже, не имеет место. Например, у нас есть 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}$ . Я ожидаю, что его коллега скажет, что A 1 , 1 ( B 1 , 2 + B 2 , 2 ) также будет вычислена. Однако это не так, поскольку его можно получить из других M k .$\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$

Буду признателен, если кто-нибудь сможет пролить свет на это.

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

$2 \times 2$

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

В книге «Теория алгебраической сложности» Бургиссера, Клаузена и Шокроллахи есть какое-то объяснение (с. 11-12). Идея состоит в том, чтобы начать с двух баз 2 , A 3 , B 0 , $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$

Я не знаю, придумал ли Штрассен такой взгляд на это. Рассматривая другие тождества, лежащие в основе быстрых алгоритмов умножения матриц, неясно, происходит ли что-то более глубокое, чем разработка какой-либо формулы. Мы уже проходили это раньше - Лагранж использовал тождество из четырех квадратов (которое было известно ранее), чтобы доказать теорему о четырех квадратах. Сначала это должна была быть просто любопытная алгебраическая идентичность, но теперь мы знаем, что она заявляет о свойстве мультипликативности кватернионной нормы. Учитывая текущее состояние знаний, трудно сказать, является ли приведенная выше интерпретация столь же продуктивной.