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

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

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

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

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

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

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

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

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

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

4 голоса | спросил Gigo 29 FebruaryEurope/MoscowbWed, 29 Feb 2012 11:00:06 +0400000000amWed, 29 Feb 2012 11:00:06 +040012 2012, 11:00:06

2 ответа


0

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

  

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

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

ответил Gigo 12 MarpmMon, 12 Mar 2012 18:33:23 +04002012-03-12T18:33:23+04:0006 2012, 18:33:23
0

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

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

ответил dranxo 29 FebruaryEurope/MoscowbWed, 29 Feb 2012 11:58:53 +0400000000amWed, 29 Feb 2012 11:58:53 +040012 2012, 11:58:53

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132