Почему матричное умножение Штрассена намного медленнее, чем стандартное умножение матрицы?
Я написал программы на С++, Python и Java для матричного умножения и протестировал их скорость для умножения двух матриц 2000 x 2000 (см. post). Стандартная ikj-имплантация - которая находится в
- взяла:
Теперь я применил алгоритм Strassen для умножения матриц - который находится в
- в Python и С++, как это было в wikipedia, Это время, которое у меня есть:
Почему матричное умножение Штрассена намного медленнее, чем стандартное умножение матрицы?
<ч/" > Идеи:
- Некоторые эффекты кеша
- Реализация:
- (результирующая матрица 2000 x 2000 верна)
- null-multipication (не должно быть так важно для 2000 x 2000 → 2048 x 2048)
Это особенно удивительно, поскольку это противоречит опыту других:
edit: причина, по которой в моем случае умножение матрицы Штрассена было медленнее:
- Я сделал это полностью рекурсивным (см. там)
- У меня было две функции
strassen
и strassenRecursive
. Первый изменил матрицу на степень двух, если требуется, и назвал вторую. Но strassenRecursive
не рекурсивно называл себя, а strassen
.
Ответы
Ответ 1
Основная проблема заключается в том, что вы переходите к размеру листа 1 с помощью вашего strassen implementaiton. Алгоритм Strassen имеет лучшую сложность Big O, но константы имеют значение на самом деле, а это означает, что на самом деле вам лучше со стандартным умножением матрицы n ^ 3 для меньших размеров проблем.
Итак, чтобы значительно улучшить вашу программу, а не делать:
if (tam == 1) {
C[0][0] = A[0][0] * B[0][0];
return;
}
используйте if (tam == LEAF_SIZE) // iterative solution here
. LEAF_SIZE
должна быть константой, которую вы должны экспериментально определить для данной архитектуры. В зависимости от архитектуры она может быть больше или меньше - существуют архитектуры, где постоянные факторы для страсса настолько велики, что в основном они всегда хуже, чем более простая реализация n ^ 3 для разумных размеров матрицы. Все зависит.
Ответ 2
Ну, "арифметические операции" - это не единственные вещи, которые считаются. Это не похоже на то, что все остальное свободно.
Мое наивное предположение было бы в том, что все это распределение и копирование памяти превосходит выигрыш от меньшего количества арифметических операций...
Доступ к памяти, в частности, может быть довольно дорогостоящим, когда он выходит из кеша. Для сравнения, арифметические операции можно считать бесплатными: -)
Ответ 3
Хотя алгоритм Штрассена имеет меньшую нотацию Big O, чтобы воспользоваться этим, вам нужно будет умножить на матрицы, которые слишком велики для решения на большинстве стандартных машин и даже суперкомпьютеров.
Подумайте об этом таким образом
одна проблема - x ^ 3, другая - X ^ 1.6734 + 8x ^ (1/2) + x.....