Метод Штрассена

[malin]

Алгоритм_Штрассена
Помогите пожалуйста, понять алгоритм.
Тяжело сформулировать вопрос, но попробую. В общем, ничего непонятного нет. Матрицы разбиваются на блоки и производится блочное умножение матриц. Потом выписываются уравнения и одно выражается через другое, что-то крутится, вертится и получаются верные равенства. При этом удается получить не 8 матричных умножений, а всего 7.

Просьба объяснить идею алгоритма, как его запомнить? Не могу просто вызубрить все эти преобразования - тяжело.

Спасибо

[Sonic86]

Википедия писал(а):

Он был разработан Штрассеном в 1969 году как обобщение метода умножения Карацубы на матрицы.

Вот собственно вся идея Идея алгоритма Карацубы Вам понятна? Просто сначала надо понять ее (а эта идея - частный случай идеи "разделяй и властвуй" (ну идиотское название, конечно, но другого общего названия вроде как нет)).

[malin]

Ну с карацубой вроде разобрался.
Сводим умножение к возведению в квадрат:
$4ab = (a+b)^2 + (b-a)^2$. А возвести в квадрат можно как-то не очень сложно..
Жаль, времени нет углубляться. С этими госэкзаменами ничего не успеваешь