Быстро разреженный булев матричный цепной продукт

13

Итак, у меня есть около 100-200 очень разреженных квадратных логических матриц с длиной стороны ~ несколько десятков, и мне нужно вычислить их произведение. Я знаю, что, если я умножу их поочередно, продукт, как правило, останется разреженным на каждом этапе.

Существуют ли какие-либо алгоритмы матричной цепочки, которые работают особенно быстро в этом случае?

На более высоком уровне проблема состоит в том, чтобы вычислить композицию ряда отображений «один ко многим» на достаточно малом графе (функции перехода NFA), где большинство элементов отображаются не более чем в 0-3.

(обратите внимание, что это не обычная проблема «матричного продукта», потому что все матрицы имеют одинаковый размер, и мне не нужно выбирать оптимальные скобки)

jkff
источник
5
на самом деле порядок их умножения может повлиять на разреженность промежуточных результатов, так что это может быть важной проблемой в любом таком быстром алгоритме.
Джошуа Грохов
из вашего другого вопроса вы, кажется, используете операции полукольца И / ИЛИ 0/1 , а не сложение / умножение (как кажется, проблема), пожалуйста, проясните это в вопросе
vzn

Ответы:

10

Это было слишком долго, чтобы быть комментарием - интересно, если эти матрицы имеют структуру, которая заставляет их вести себя иначе, чем случайные матрицы. Произведения случайных разреженных матриц стремятся к нулю или быстро становятся не разреженными.

Вот простой эксперимент - возьмите 200 случайных двоичных матриц размером 50x50 и построите число ненулевых функций как функцию от числа умноженных матриц. Графики ниже показывают стандартное отклонение за 2000 прогонов. Первый участок для 2% разреженности, второй участок для 3%


(источник: yaroslavvb.com ) (источник: yaroslavvb.com )

это заняло 3 минуты на моем ноутбуке с использованием стандартного умножения матриц

Ярослав Булатов
источник