Итак, у меня есть около 100-200 очень разреженных квадратных логических матриц с длиной стороны ~ несколько десятков, и мне нужно вычислить их произведение. Я знаю, что, если я умножу их поочередно, продукт, как правило, останется разреженным на каждом этапе.
Существуют ли какие-либо алгоритмы матричной цепочки, которые работают особенно быстро в этом случае?
На более высоком уровне проблема состоит в том, чтобы вычислить композицию ряда отображений «один ко многим» на достаточно малом графе (функции перехода NFA), где большинство элементов отображаются не более чем в 0-3.
(обратите внимание, что это не обычная проблема «матричного продукта», потому что все матрицы имеют одинаковый размер, и мне не нужно выбирать оптимальные скобки)
Ответы:
Это было слишком долго, чтобы быть комментарием - интересно, если эти матрицы имеют структуру, которая заставляет их вести себя иначе, чем случайные матрицы. Произведения случайных разреженных матриц стремятся к нулю или быстро становятся не разреженными.
Вот простой эксперимент - возьмите 200 случайных двоичных матриц размером 50x50 и построите число ненулевых функций как функцию от числа умноженных матриц. Графики ниже показывают стандартное отклонение за 2000 прогонов. Первый участок для 2% разреженности, второй участок для 3%
(источник: yaroslavvb.com ) (источник: yaroslavvb.com )
это заняло 3 минуты на моем ноутбуке с использованием стандартного умножения матриц
источник