Эта формула, в отличие от формулы Винограда, не опирается на коммутативность умножения; поэтому можно 2п ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Кнут Д.N. Искусство программирования для ЭВМ Том 2


Эта формула, в отличие от формулы Винограда, не опирается на коммутативность умножения; поэтому можно 2п х 2п - матрицу разбить на четыре пхл-блока и затем рекурсивно использовать предыдущее тождество. Следовательно, мы можем умножить 2 X 2 -матрицы, применив только 7 умножений и 6 ( 7 - 4й) сложений; общее число операций, потребных для умножения nxn - матриц, снижается, таким образом, до величины 0 ( rtlo f7) О ( л2 81), что для больших п дает существенную экономию времени.

(cкачать страницу)

Смотреть книгу на libgen

Эта формула,  в отличие от формулы Винограда,  не опирается на коммутативность умножения;  поэтому можно 2п х 2п - матрицу разбить на четыре пхл-блока и затем рекурсивно использовать предыдущее тождество.  Следовательно,  мы можем умножить 2 X 2 -матрицы,  применив только 7 умножений и 6 ( 7  -  4й) сложений;  общее число операций,  потребных для умножения nxn - матриц,  снижается,  таким образом,  до величины 0 ( rtlo f7) О ( л2 81),  что для больших п дает существенную экономию времени.