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

17

В алгоритме Штрассена, чтобы вычислить произведение двух матриц и B , матрицы A и B делятся на блочные матрицы 2 × 2, и алгоритм продолжает рекурсивное вычисление 7- блочных матрично-матричных произведений, а не наивных 8- блочных матричных матриц. матричные произведения, т. е. если мы хотим C = A B , где A = [ A 1 , 1 A 1 , 2 A 2 , 1 A 2 , 2AВAВ2×278Сзнак равноAВ тогда мы имеем C 1 , 1 = A 1 , 1 B 1 , 1 + A 1

Aзнак равно[A1,1A1,2A2,1A2,2] , Взнак равно[В1,1В1,2В2,1В2,2] , Сзнак равно[С1,1С1,2С2,1С2,2]
что требует8умножений. Вместо этого в Штрассене мы вычисляем M 1 :=( A 1 , 1 + A 2 , 2 )( B 1 , 1 + B 2 , 2 )
С1,1знак равноA1,1В1,1+A1,2В2,1С1,2знак равноA1,1В1,2+A1,2В2,2С2,1знак равноA2,1В1,1+A2,2В2,1С2,2знак равноA2,1В1,2+A2,2В2,2
8 и получить C i , j , используя M k в качестве C 1 , 1 = M 1 + M 4 - М 5 + М 7
M1знак равно(A1,1+A2,2)(В1,1+В2,2)M2знак равно(A2,1+A2,2)В1,1M3знак равноA1,1(В1,2-В2,2)M4знак равноA2,2(В2,1-В1,1)M5знак равно(A1,1+A1,2)В2,2M6знак равно(A2,1-A1,1)(В1,1+В1,2)M7знак равно(A1,2-A2,2)(В2,1+В2,2)
Ся,JMК Однако выбор матриц M k мне кажется произвольным. Есть ли общая картина, почему мы выбираем эти конкретные произведения подматриц A и B ? Кроме того, я ожидал бы, что M k будет задействовать A i , j и B i , j симметрично, что, похоже, не имеет место. Например, у нас есть M 2 :=
С1,1знак равноM1+M4-M5+M7С1,2знак равноM3+M5С2,1знак равноM2+M4С2,2знак равноM1-M2+M3+M6
MКAВMКAя,JВя,J . Я ожидаю, что его коллега скажет, что A 1 , 1 ( B 1 , 2 + B 2 , 2 ) также будет вычислена. Однако это не так, поскольку его можно получить из других M k .M2знак равно(A2,1+A2,2)В1,1A1,1(В1,2+В2,2)MК

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

Сообщество
источник

Ответы:

15

2×22×2

2×2

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

Маркус Блезер
источник
11

В книге «Теория алгебраической сложности» Бургиссера, Клаузена и Шокроллахи есть какое-то объяснение (с. 11-12). Идея состоит в том, чтобы начать с двух баз 2 , A 3 , B 0 , BA0,A1,A2,A3В0,В1,В2,В32×2AяВJ{0,A0,A1,A2,A3,В0,В1,В2,В3}A0знак равноВ0AВA0знак равноВ0,A1,A2,A3,В1,В2,В3M

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

Юваль Фильмус
источник
3
2×2