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

Question

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

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

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

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

Другая идея, которую я нашел в Википедии была суммируя все элементы Адамара, т.е. начального мудрая умножения, но я не знают, как продлить этот метод к силе 3 и 4.

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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