алгоритм шёнхаге-штрассена

[Dongara]

Xaositect в сообщении #261299 писал(а):

Dongara в сообщении #261237 писал(а):

Посмотрел. Работу далекого 1976 года я знаю. Но и она и предложенный здесь подход работают хорошо в ассимптотике. Для реальных матриц (в смысле их размера), с которыми имеет дело нынешнее человечество, это не выход (в смысле выигрыша в скорости). Я нашел одну ссылку на русскоязычном форуме Интела по решению этой проблемы, но товарищ делиться секретом не хочет.

Я думаю, несколько итераций алгоритма Штрассена, а затем использование обычного умножения, даст некоторый прирост скорости.
А какой сейчас размер матриц на практике? мне на втором курсе(три года назад) говорили про десятки тысяч, но, возможно, это была устаревшая информация.

Разумный компромисс определяется скоростью памяти, эффективностью распараллеливания и требуемой точностью, чему я и следую в реализации своих алгоритмов. У меня 8 гигов памяти и 4-ядерный процессор. Матрицы у меня небольшие - порядка 16000*16000, так что все умещается в памяти.

[Xaositect]

Я сам теоретик, поэтому на своем опыте не могу ничего сказать. Один мой знакомый реализовывал на какой-то архитектуре, где один главный процессор и 8 вспомогательных, умножение таким образом: одна итерация по методу Штрассена, 7 умножений раскидываются по вспомогательным процессорам и там умножается обычным методом.

[Dongara]

Xaositect в сообщении #261376 писал(а):

Я сам теоретик, поэтому на своем опыте не могу ничего сказать. Один мой знакомый реализовывал на какой-то архитектуре, где один главный процессор и 8 вспомогательных, умножение таким образом: одна итерация по методу Штрассена, 7 умножений раскидываются по вспомогательным процессорам и там умножается обычным методом.

Ну, Ваш знакомый крайне примитивно подошел к реализации алгоритма, хотя для малых матриц этот подход и может быть оправдан. Конечно я имею в виду модель с общей памятью. Особо сложного здесь ничего нет: требуемая точность расчета определяет глубину рекурсии, а скорость памяти и эффективность распараллеливания (которые тоже могут влиять на глубину рекурсии) уже необходимы на листочках дерева рекурсии, где требуется крайне эффективный метод умножения матриц.

[Chifu]

А чем не нравится умножение столбиком? Распространяется на любую разрядность процессора, есть возможность распараллеливания. Есть 3 варианта: 1. Сложение частичных сумм. 2. Сложение перестановок. 3. Модификация дерева умножения. С помощью FFT по-моему погрешность метода возникнет.