Как быстро умножают края матриц?

Question

[qoqo]

Добрый день, подскажите пожалуйста , как умножать края матриц . Есть алгоритм умножения матриц, но он работает с матрицами , размеры которых кратны 8 . Сейчас я умножаю края наивным алгоритмом , но скорость маленькая . Есть ли какие нибудь алгоритмы ?

Comments

[mayton2019]

Ты лучше покажи свой алгоритм. Так будет быстрее.

[Lynn «Кофеман»]

И что такое умножение краев матриц?

Answer 1

[Wataru]

Можно дополнить матрицы нулями до размера кратного 8. Так (но со степенью двойки) работает умножение через быстрое преобразование фурье, например.

Или можно наивно последние 1-7 слагаемых в каждой сумме подсчитать. Это займет O(n^2), что по сравнению с остальным алгоритмом - копейки.

Comments

[rPman]

быстрое преобразование фурье

каким боком алгоритм работы с гармоническими колебаниями тут применим?

[Wataru]

rPman, Ох, напутал я. Для произведения матриц оно не применимо, но перемножение полиномов, длинных чисел и свертки на матрицах - делаются через FFT. Есть какие-то извращенные алгоритмы вроде этого (страница 31+), но это совсем не то, что я представлял, когда упоминал FFT выше.