Алгоритм Штрассена для умножения матриц

Question

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

Answer 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 не станет всем, что нам осталось. Чудесным образом М выбираются так, чтобы M1+M7-M2+M5 работал. То же самое с другими 3 необходимыми результатами.

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

Answer 2

На мой взгляд, есть 3 идеи, которые нужно получить:

1. Вы можете разбить матрицу на блоки и работать с полученной матрицей блоков так же, как с матрицей чисел. В частности, вы можете умножить две такие матрицы блоков (конечно, при условии, что количество строк блока в одной соответствует количеству столбцов блока в другой) и получить тот же результат, что и при умножении исходных матриц чисел.

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

3. Рекурсия.

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

Answer 3

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

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

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