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

Рассмотрим умножение двух матриц 2x2, как показано ниже:

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

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

Вот семь умножений:

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. То же самое с другими тремя необходимыми результатами.

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

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

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

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

In my opinion there are 3 ideas that you need to get:

1. You can split a matrix into blocks and operate on the resulting matrix of blocks like you would on a matrix of numbers. In particular you can multiply two such block matrices (of course as long as the number of block rows in one matches the number of block columns in the other) and get the same result as you would when multiplying original matrices of numbers.

2. The blocks necessary to express the result of 2x2 block matrix multiplication have enough common factors to allow computing them in fewer multiplications than the original formula implies. This is the trick described in Tony's answer.

3. Recursion.

Strassen algorithm is just an application of the above. To understand the analysis of its complexity, you need to read "Concrete Mathematics" by Ronald Graham, Donald Knuth, and Oren Patashnik or a similar book.