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

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

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

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

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

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

См. http://en.wikipedia.org/wiki/Trace_(linear_алгебра)#Properties< /а>

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

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

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


optimization math linear-algebra mathematical-optimization adjacency-matrix
person Gigo    schedule 29.02.2012    source источник
comment
Матрица какого размера?   -  person    schedule 29.02.2012
comment
Читая более внимательно, я запутался. Вы говорите, что матрица диагональная, с нулевыми диагональными элементами. Что это? Диагональная матрица с нулями по диагонали имеет довольно простой след: НОЛЬ. Любая степень нулевой матрицы также имеет нулевой след. Вы имели в виду, что матрица симметрична, а не диагональна?   -  person    schedule 29.02.2012
comment
Поскольку это матрица смежности, размер зависит от размера графа. Самый большой, который я использовал, был 1600x1600.   -  person Gigo    schedule 29.02.2012
comment
Я думаю, что это принадлежит scicomp.stackexchange.com   -  person John Alexiou    schedule 29.02.2012

Ответы (2)


arrow_upward
2
arrow_downward

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

То есть, если 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/

person dranxo    schedule 29.02.2012

arrow_upward
1
arrow_downward

Хорошо, я только что понял это сам. Главное, чего я не знал, это:

Если 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) при работе с разреженными графами и использовании списков смежности вместо матриц.

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

person Gigo    schedule 12.03.2012
comment
У вас есть разреженный граф, поэтому у вас есть разреженная матрица смежности. В этом случае умножение матриц выполняется очень быстро. Вы уверены, что эта идея с перечислением путей будет быстрее, чем просто вычисление A^3? - person dranxo; 19.03.2012