Почему матричное умножение Штрассена намного медленнее, чем стандартное умножение матрицы?

Я написал программы на С++, Python и Java для матричного умножения и протестировал их скорость для умножения двух матриц 2000 x 2000 (см. post). Стандартная ikj-имплантация - которая находится в - взяла:

С++: 15 секунд (Источник)
Python: 6 минут 13 секунд (Источник)

Теперь я применил алгоритм Strassen для умножения матриц - который находится в - в Python и С++, как это было в wikipedia, Это время, которое у меня есть:

С++: 45 минут (Источник)
Python: убит через 10 часов (Источник)

Почему матричное умножение Штрассена намного медленнее, чем стандартное умножение матрицы?

<ч/" > Идеи:

Некоторые эффекты кеша
Реализация:
- (результирующая матрица 2000 x 2000 верна)
- null-multipication (не должно быть так важно для 2000 x 2000 → 2048 x 2048)

Это особенно удивительно, поскольку это противоречит опыту других:

Почему мой мультипликатор Matrix Strassen так быстро?
Матричное умножение: Штрассен против Стандарта - Штрассен был еще медленнее для него, но он был, по крайней мере, в том же порядке.

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.....