Методът на четиримата руснаци за матрично умножение
Ако разгледаме произведението на матрици [math] C = A \ cdot B [/ math] по дефиниция [math] \ left (c_ = \ sum \ limit_ ^ n a_b_ \ right) [/ math], тогава сложността на алгоритъмът ще бъде [math] O (n ^ 3) [/ math] - всеки от [math] n ^ 2 [/ math] елементите на получената матрица [math] C [/ math] се изчислява във време, пропорционално на [ математика] n [/ математика] .
Сега ще бъде показано как леко да намалим това време.
За да извършим компресиране на матрици, извършваме следното предварително изчисление: за всички възможни двойки двоични вектори с дължина [math] k [/ math], изчисляваме и съхраняваме техния скаларен продукт по модул [math] 2 [/ math] .
Да вземем първата матрица. разделете всяка от линиите му на парчета с размер [math] k [/ math]. За всяка фигура определяме номера на двоичния вектор, който съответства на числата на тази фигура. Ако парчето е неравномерно по дължина [math] k [/ math] (последното парче от реда), тогава ще приемем, че в края съдържа нули, които не влияят на умножението. Получаваме матрицата [math] A'_ \ rceil> [/ math] .
Нека направим същото с матрицата [math] B [/ math], разделяйки колони вместо редове. Получаваме матрицата [math] B '_ [/ math] .
Сега, ако вместо произведението на матриците [math] A [/ math] и [math] B [/ math], ние разглеждаме произведението на новите матрици [math] A '[/ math] и [math] B '[/ math], използвайки изчислените скаларни продукти, тогава всеки елемент от матрицата [math] C [/ math] ще бъде получен вече във време, пропорционално на [math] \ lceil \ dfrac \ rceil [/ math] вместо [ math] n [/ math], а времето на матричния продукт ще бъде намалено от [math] O (n ^ 3) [/ math] на [math] O (n ^ 2 \ cdot \ dfrac nk) = O (\ dfrac) [/ математика] .
