быстрое матричное умножение

[allchemist]

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

С практической точки зрения, насколько большой профит от использования подобных методов вместо копперсмитовского, и от использования копперсмитовского вместо штрассена?

-- Чт апр 08, 2010 20:07:02 --

кстати, в blas (gemm) который алгоритм реализован?

[venco]

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

[Zealint]

allchemist в сообщении #307767 писал(а):

кстати, в blas (gemm) который алгоритм реализован?

Мне знакомый сказал, что там кубическое перемножение. Попробуйте сами: увеличивайте порядок матрицы вдвое и наблюдайте как время работы растёт в 8 раз. Штук 10 больших испытаний, наверное, будет достаточно.