Нахождение k-наименьших собственных значений и соответствующего им собственного вектора для большой матрицы

Для симметричной разреженной квадратной матрицы размером 300 000 * 300 000, как лучше всего найти 10 наименьших собственных значений и соответствующие им собственные векторы в течение часа или около того на любом языке или в любом пакете.


sparse-matrix eigenvalue eigenvector
person bemma    schedule 27.03.2019    source источник
comment
Взгляните на это: github.com/yixuan/spectra (сам никогда не пробовал, но это кажется именно то, что вам нужно)   -  person chtz    schedule 27.03.2019
comment
@chtz Спасибо за помощь, но похоже, что это для K наибольших собственных значений или для всех. Вместо вычисления всех собственных значений мне просто нужно K наименьших собственных значений и соответствующих им векторов.   -  person bemma    schedule 27.03.2019
comment
Согласно документу, он также поддерживает вычисление собственных значений, ближайших к 0: github.com /yixuan/spectra#shift-and-invert-mode   -  person chtz    schedule 27.03.2019

Ответы (1)


arrow_upward
1
arrow_downward

Алгоритм Ланцоша, работающий с эрмитовой матрицей, является хорошим способом найти наименьшее и наибольшее собственные значения и соответствующие собственные векторы. Обратите внимание, что реальная симметричная матрица по определению является эрмитовой. Ланцошу требуется O(N) памяти, а также примерно O(N) времени для оценки экстремальных собственных значений/собственных векторов. Это контрастирует с диагонализацией грубой силы, которая требует O(N^2) памяти и O(N^3) времени работы. По этой причине алгоритм Ланцоша сделал возможным приближенное решение многих задач, которые ранее были невозможны с вычислительной точки зрения.

Вот полезная ссылка на сайт Калифорнийского университета в Дэвисе, в котором перечислены реализации Lanczos на нескольких языках/пакетах, включая FORTRAN, C/C++ и MATLAB.

person Tim Biegeleisen    schedule 27.03.2019
comment
Спасибо. Он работает идеально. Моя матрица представляет собой матрицу Лапласа графа. Когда я пытаюсь найти k наименьших собственных значений, это дает мне ошибку: Первая входная матрица является единственной. Сдвиг 0 является собственным значением. Рассмотрите возможность использования ненулевого числового значения для сигмы. Есть ли способ вычислить k-наименьших собственных значений в этом случае. - person bemma; 27.03.2019
comment
Не уверен, но, возможно, ваши данные таковы, что они не будут работать с Ланцошем. - person Tim Biegeleisen; 27.03.2019
comment
Каким-то образом это работает идеально, и это дает мне ошибку [...], противоречащую друг другу. Вы пробовали ненулевое значение для сигмы, как предполагает ошибка? - person chtz; 27.03.2019
comment
@chtz sigma соответствует другому выбору собственных значений. Для сигмы = 'sm', т.е. сигма = 0 соответствует наименьшей величине, которая интересует. Он работает для других значений сигмы очень быстро. - person bemma; 27.03.2019
comment
@bemma, да, я понимаю. Вы пробовали, например, 1e-6 или -1e-6? (не знаю, насколько близки к нулю ваши электромобили) - person chtz; 27.03.2019
comment
@chtz Спасибо, с 1e-6 ошибка не возникает, занимая бит больше, чем k самое большое. - person bemma; 27.03.2019