Как умножить огромные матрицы?

Question

[Мария]

Подскажите, пожалуйста, как вычислить произведение двух матриц одинаковой размерности 2в10 x 2в10. Классический подход не работает - не хватает памяти.
Язык: C++

Comments

[rPman]

огромные - это 10^10, а у вас всего миллион элементов, или вы пишете код под контроллер с 2кб оперативной памяти?.

Answer 1

[Ярослав]

А на что не хватает памяти? На хранение матриц?

Возможно, если матрицы разрежённые (т.е. в основном заполнены нулями), проще будет хранить только ненулевые значения в хэш-таблице (да в той же std::map).
В качестве ключа можно использовать пару индексов (i,j).
Если с таким ключом значения в хэш-таблице нет, считаем, что там лежит ноль.

Если матрица - 1024 х 1024, и в ней всего пара ненулевых значений - экономия памяти будет огромной.
Главное не забывать в результирующей матрице тоже хранить только _ненулевые_ значения.

Answer 2

[rhaport]

Вам метод Штрассена в помощь

https://ru.m.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3...

Сколько у вас памяти есть?