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

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), затем добавьте / вычтите некоторые из других M, пока 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)? Один, верно? Но они одно и то же выражение!

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