Вычисление N наименьших собственных значений разреженной матрицы в Python

Я хотел бы найти N наименьших собственных значений разреженной матрицы в Python. Я пробовал использовать пакет scipy.sparse.linalg.eigen.arpack, но он очень медленно вычисляет наименьшие собственные значения. Я где-то читал, что существует режим инвертирования сдвига, но когда я пытаюсь его использовать, я получаю сообщение об ошибке, в котором говорится, что режим инвертирования сдвига еще не поддерживается. Любые идеи относительно того, как я должен действовать?


python scipy sparse-matrix eigenvalue
person Eliezer    schedule 31.01.2012    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Версии SciPy

Сравнение документации scipy.sparse.linalg.eigs из SciPy v0.9 с документацией scipy.sparse.linalg.eigs from SciPy v0.10 похоже, что режим сдвига-инвертирования реализован и работает с версии v0.10. В частности, объяснение параметра sigma в документации версии 0.9 гласит, что он не реализован, но в документации версии 0.10 это не указано.

Если у вас нет SciPy v0.10 или более поздней версии, установка последней версии должна позволить вам использовать режим сдвига-инверсии с разреженным собственным решателем.

Медленный поиск собственных значений малой величины

Как упоминалось в вопросе, можно использовать интерфейс ARPACK для поиска собственных значений малой величины. Это делается путем передачи which='SM' при вызове scipy.sparse.linalg.eigs. Однако, как указано в вопросе, он медленный. Это подтверждается в разделе учебника по SciPy, посвященном проблемам с разреженными собственными значениями в ARPACK, где указано:

Обратите внимание, что ARPACK обычно лучше находит экстремальные собственные значения, то есть собственные значения с большими величинами. В частности, использование which = 'SM' может привести к замедлению времени выполнения и/или аномальным результатам. Лучше использовать режим инвертирования сдвига.

Эксперименты

Давайте посмотрим на некоторый код, пытающийся использовать сдвиг-инвертирование как с версиями 0.9, так и с версиями 0.10 SciPy. В обоих случаях мы будем использовать следующий код.

from scipy.sparse import identity
from scipy.sparse.linalg import eigs

A = identity(10, format='csc')
A.setdiag(range(1, 11))
eigs(A, 3, sigma=0) # find three eigenvalues near zero using shift-invert mode

SciPy v0.9

Запуск кода в SciPy v0.9 приводит к возникновению исключения.

NotImplementedError: shifted eigenproblem not supported yet

SciPy v0.10

Запуск кода в SciPy 0.10 дает ожидаемые результаты.

(array([ 1.+0.j,  2.+0.j,  3.+0.j]),
 array([[ -1.00000000e+00+0.j,   5.96300068e-17+0.j,   9.95488924e-17+0.j],
       [  3.55591776e-17+0.j,   1.00000000e+00+0.j,  -4.88997616e-16+0.j],
       [ -3.79110898e-17+0.j,   1.16635626e-16+0.j,   1.00000000e+00+0.j],
       [ -1.08397454e-17+0.j,   1.23544164e-17+0.j,   1.78854096e-15+0.j],
       [  1.68486368e-17+0.j,  -9.37965967e-18+0.j,   2.05571432e-16+0.j],
       [ -2.97859557e-19+0.j,  -3.43100887e-18+0.j,   3.35947574e-17+0.j],
       [  1.89565432e-17+0.j,  -3.61479402e-17+0.j,  -1.33021453e-17+0.j],
       [ -1.40925577e-18+0.j,   3.16953070e-18+0.j,   7.91193025e-17+0.j],
       [  6.76947854e-19+0.j,  -3.75674631e-19+0.j,   3.61821551e-17+0.j],
       [ -3.07505146e-17+0.j,  -6.52050102e-17+0.j,  -8.57423599e-16+0.j]]))
person David Alber    schedule 01.02.2012