Вычисление следа матрицы к степени k

Question

Мне нужно вычислить трассу матрицы в степени 3 и 4, и она должна быть настолько быстрой, насколько это возможно.

Матрица здесь - это матрица смежности простого графа, поэтомуон квадратный, симметричный, его записи всегда равны 1 или 0, а диагональные элементы всегда равны 0.

Оптимизация тривиальна для трассы матрицы до степени 2:

• Нам нужны только диагональные записи (i, i) для трассы, пропустите все остальные
• Поскольку матрица симметрична, эти записи являются просто записями i-й строки в квадрате и суммируются
• И так как записи равны только 1 или 0, квадратную операцию можно пропустить

Еще одна идея, которую я нашел в википедии, заключалась в суммировании всех элементов произведения Адамара, то есть умножении по вхождению, ноЯ не знаю, как расширить этот метод до степени 3 и 4.

См. http://en.wikipedia.org/wiki/Trace_(linear_algebra)#Properties

Возможно, я просто слепой, но не могу придумать простого решения.

В конце мне нужно реализовать C ++Примечание, но я думаю, что это не важно для вопроса.

Заранее спасибо за любую помощь.

Answer 1

Трасса представляет собой сумму собственных значений, а собственные значения мощности матрицы являются просто собственными значениями этой мощности.

То есть, если l_1, ..., l_n - собственные значения вашей матрицы, то trace (M ^ p) = 1_1 ^ p + l_2 ^ p + ... + l_n ^ p.

В зависимости от вашей матрицы вы можете захотеть вычислить собственные значения и затем сложить. Если ваша матрица имеет низкий ранг (или может быть хорошо аппроксимирована матрицей с низким рангом), вы можете вычислить собственные значения очень дешево (частичное разложение имеет сложность O (n * k ^ 2), где k - ранг).

Редактировать: Вы упоминаете в комментариях, что это 1600x1600, и в этом случае поиск всех собственных значений не должен быть проблемой. Вот один из многих кодов C ++, которые вы можете использовать для этого http://code.google.com/p/redsvd/

Answer 2

Хорошо, я только что понял это сам.Важная вещь, которую я не знал, заключалась в следующем:

Если A - матрица смежности ориентированного или ненаправленного графа G, то матрица An (т. Е. Матричное произведение n копий A) имеетинтересная интерпретация: запись в строке i и столбце j дает количество (направленных или ненаправленных) переходов длины n от вершины i до вершины j.Это подразумевает, например, что количество треугольников в неориентированном графе G является в точности следом A ^ 3, деленным на 6.

(Скопировано из http://en.wikipedia.org/wiki/Adjacency_matrix#Properties)

Получениеколичество путей заданной длины от узла i до i для всех n узлов по существу можно сделать в O (n) при работе с разреженными графами и использованием списков смежности вместо матриц.

Тем не менее, спасибо за вашеответы!