Какой самый быстрый способ вычислить все собственные значения очень большой и разреженной матрицы смежности в python?

Я пытаюсь выяснить, существует ли более быстрый способ вычисления всех собственных значений и собственных векторов очень большой и разреженной матрицы смежности, чем использование scipy.sparse.linalg.eigsh. Насколько я знаю, этот метод использует только разреженность и атрибуты симметрии матрицы. Матрица смежности также является двоичной, что заставляет меня думать, что есть более быстрый способ сделать это.

Я создал случайную матрицу разреженной смежности 1000x1000 и сравнил несколько методов на своем ноутбуке x230 Ubuntu 13.04:

scipy.sparse.linalg.eigs: 0,65 секунд
scipy.sparse.linalg.eigsh: 0,44 секунды
scipy.linalg.eig: 6,09 секунд
scipy.linalg.eigh: 1,60 секунды

С разреженными eigs и eigsh я устанавливаю k, число желаемых собственных значений и собственных векторов, чтобы быть рангом матрицы.

Проблема начинается с более крупных матриц - на матрице 9000x9000 это заняло у scipy.sparse.linalg.eigsh 45 минут!

linear-algebra python performance eigensystem scipy Ноам Пелед
источник

NB. scipy.sparse.linalg.eigsh - это ARPACK

pv.

Для этого, чем больше ваша матрица, тем меньше вероятность того, что вы точно рассчитаете внутренние собственные значения (то есть ни самые большие, ни наименьшие собственные значения). Какая информация вам нужна из матрицы, которую вы разлагаете?

Джефф Оксберри

Этот вопрос был кросс-пост здесь . Я собираюсь рекомендовать, чтобы кросс-опубликованная версия была закрыта.

Арон Ахмадиа

Я хочу вычислить A ^ k. После переосмысления, я думаю, с такой матрицей гораздо быстрее вычислить прямое умножение (A A A ...), чем с помощью собственного разложения. Конечно, это зависит от k.

Ноам Пелед

Да, делай это напрямую. Результаты собственного разложения не редки, поэтому у вас будут проблемы с памятью (опять же, A ^ k, если k достаточно велико). Связанный stackoverflow.com/a/9495457/424631

dranxo

Ответы:

FILTLAN - это библиотека C ++ для вычисления внутренних собственных значений разреженных симметричных матриц. Тот факт, что есть целый пакет, посвященный именно этому, должен сказать вам, что это довольно сложная проблема. Нахождение наибольшего или наименьшего числа собственных значений симметричной матрицы может быть выполнено путем сдвига / инвертирования и использования алгоритма Ланцоша, но середина спектра - это другой вопрос. Если вы хотите использовать это, вы можете использовать SWIG для вызова программы на C ++ из python.

Если ваша конечная цель состоит в том, чтобы вычислить большие степени матрицы, вы можете просто вычислить собственные векторы, соответствующие наибольшим собственным значениям, учитывая, что меньшие моды будут менее важны, поскольку вы принимаете большие степени.

$k$

Простите, если это уже очевидно для вас: вы можете использовать двоичную природу матрицы, сказав numpy, что она состоит из целых чисел, а не чисел с плавающей запятой, скажем, с помощью

a = np.zeros(100,dtype=np.uint)

$A^{16}$ $A^2$ $A^4$ $A^8$ $\approx\log_2 k$ $k$

Вы также можете исследовать вызов библиотеки параллельной разреженной линейной алгебры, такой как CUSP или cuSPARSE из Python, если вам важна скорость и у вас есть графический процессор NVIDIA.

Даниэль Шаперо
источник

Я хотел бы прокомментировать ответ Даниэля Шаперо, но мне не хватает репутации SE.

Принятый ответ меня сильно смущает. Я думаю, что режим смещения-сдвига может быть легко использован для вычисления внутренних собственных значений. См .: https://docs.scipy.org/doc/scipy/reference/tutorial/arpack.html.

Чтобы ответить на исходный вопрос: редко случается так, что вам нужны все собственные значения большой разреженной матрицы. Обычно вам нужны экстремумы или некоторый кластер внутренних значений. В таком случае для эрмитовой матрицы eigshэто быстрее. Для не-эрмитян вам придется пойти с eigs. И они намного быстрее, чем NumPy eigили eigh.

Alex
источник