Алгоритм Strassen для матричного умножения

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

Ответ 1

Рассмотрим умножение двух матриц 2x2 следующим образом:

A B * E F = AE+BG AF+BH
C D   G H   CE+DG CF+DH

Очевидным способом вычислить правую сторону является просто 8 умножений и 4 добавления. Но представьте, что множители намного дороже, чем дополнения, поэтому мы хотим уменьшить количество умножений, если это вообще возможно. Штрасс использует трюк, чтобы вычислить правую сторону с одним меньшим умножением и намного большим количеством дополнений (и некоторыми вычитаниями).

Вот 7 умножений:

M1 = (A + D) * (E + H) = AE + AH + DE + DH
M2 = (A + B) * H = AH + BH
M3 = (C + D) * E = CE + DE
M4 = A * (F - H) = AF - AH
M5 = D * (G - E) = DG - DE
M6 = (C - A) * (E + F) = CE + CF - AE - AF
M7 = (B - D) * (G + H) = BG + BH - DG - DH

Итак, чтобы вычислить AE + BG, начните с M1 + M7 (который получит нам условия AE и BG), затем добавьте/вычтите часть других Ms до тех пор, пока AE + BG не останется с нами. Чудом M выбирается так, что M1 + M7-M2 + M5 работает. То же самое с другими 3 требуемыми результатами.

Теперь просто поймите, что это работает не только для матриц 2x2, но и для любых (четных) размерных матриц, где A..H являются подматрицами.

Ответ 2

По моему мнению, есть 3 идеи, которые вам нужно получить:

Вы можете разбить матрицу на блоки и работать с результирующей матрицей блоков, как и на матрице чисел. В частности, вы можете умножить две такие матричные матрицы (конечно, если количество строк блока в одном соответствует числу столбцов блока в другом) и получить тот же результат, что и при умножении исходных матриц чисел.
Блоки, необходимые для выражения результата умножения блочной матрицы 2x2, имеют достаточно общие факторы, позволяющие вычислять их с меньшим количеством умножений, чем подразумевает исходная формула. Это трюк, описанный в ответ Тони.
Рекурсия.

Алгоритм Штрассена - это просто применение вышеуказанного. Чтобы понять анализ его сложности, вам нужно прочитать " Concrete Mathematics" Рональд Грэм", Дональд Кнут и Орен Паташник или аналогичная книга.

Ответ 3

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

Вот аналогия. Сколько умножений в x*x + 5*x + 6? Два, верно? Сколько умножений в (x+2)(x+3)? Один, верно? Но это одно и то же выражение!

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