Эффективный продукт 3 разреженных матриц, который создает плотный промежуточный

Question

У меня есть 3 матрицы, которые все разрежены: A, B и C.

Мне нужно взять матричное произведение AB, что приводит к плотной матрице. После этого мне нужно элементное произведение AB (элементное *) C. C является разреженным, и поэтому поэлементное умножение обнулит большую часть плотного произведения AB, что снова приведет к разреженной матрице.

Зная это, я пытаюсь выяснить, как не материализовать все плотные компоненты AB.

Если C_ {i, J} равно 0, то я не должен материализовать AB_ {Я, J}. Это означает, что я могу пропустить скалярное произведение A_ {row i} и B_ {col j}. Но, кажется, очень неэффективно писать для l oop над строками A, чтобы выбрать строки, которые я хочу материализовать.

Может ли быть другой способ сделать это умножение разумно?

Вот пример генератора данных в R, хотя реальный продукт AB, который у меня есть, более плотный, чем этот генератор. FWIW помощь от любого языка программирования была бы полезна, не обязательно R. (Эйген был бы великолепен, хотя!)

require(Matrix)

n = 10000
p = 100
A = rsparsematrix(n, p, .1)
B = rsparsematrix(p, p, .1)
C = rsparsematrix(n, p, .1)

Answer 1

Это довольно тесно связано с подсчетом треугольников. Если бы A, B и C были бинарными матрицами, вы могли бы интерпретировать их как матрицы смежности для трехстороннего графа и подсчитать для каждого ребра в C сколько треугольников оно принадлежит.

Возможно в R существует обнаружение сообщества с подсчетом треугольников, которое можно адаптировать к вашему варианту использования.

Под такой библиотекой, вероятно, есть следующий трюк (на который я должен ссылаться, но не от руки). Это включает в себя сортировку узлов графа по степени и направление всех исходящих ребер от низкой степени к высокой. Затем для каждого узла вы проверяете каждую пару исходящих ребер (клин) на ребро, которое его завершит.