Эффективный алгоритм нахождения наибольшей собственной пары малой общей комплексной матрицы

Question

Я ищу эффективный алгоритм для нахождения наибольшей собственной пары небольшой, общей (не квадратной, не разреженной, несимметричной) комплексной матрицы A размера m x n. Под малым я подразумеваю, что m и n обычно составляют от 4 до 64 и обычно около 16, но с m не равно n. Эту проблему легко решить с помощью общих алгоритмов LAPACK SVD, то есть gesvd или gesdd. Однако, поскольку я решаю миллионы этих проблем и требую только самую большую собственную пару, я ищу более эффективный алгоритм. Кроме того, в моем приложении собственные векторы, как правило, будут одинаковыми для всех случаев. Это привело меня к исследованию методов, основанных на итерациях Арнольди, но я не нашел ни хорошей библиотеки, ни алгоритма, который применим к моей небольшой общей сложной матрице. Есть ли подходящий алгоритм и / или библиотека?

Answer 1

Релеевская итерация имеет кубическую сходимость. Возможно, вы захотите также реализовать метод power и посмотреть, как они сравниваются, так как вам нужно LU или QR-разложение вашей матрицы.

http://en.wikipedia.org/wiki/Rayleigh_quotient_iteration

После комментария @ rchilton вы можете применить это к A * A.

Answer 2

Идея поиска наибольшей собственной пары аналогична нахождению большой мощности матрицы, поскольку низкочастотные моды затухают во время итерации.Алгоритм Ланцоша является одним из немногих таких алгоритмов, которые полагаются на так называемые собственные векторы Ритца при разложении.Из Википедии:

Алгоритм Ланцоша является итеративным алгоритмом ... который представляет собой адаптацию степенных методов для поиска собственных значений и собственных векторов квадратной матрицы или разложения по сингулярным числам прямоугольной матрицы.Это особенно полезно для нахождения разложений очень больших разреженных матриц.Например, в скрытой семантической индексации матрицы, связывающие миллионы документов с сотнями тысяч терминов, должны быть преобразованы в форму единственного значения.

Этот метод работает, даже если система не разреженный, но если он большой и плотный, он имеет то преимущество, что не все должны быть сохранены в памяти одновременно.

Как это работает?

Степенной метод определения наибольшего собственного значения матрицы A можно обобщить, отметив, что если x_ {0} является случайным вектором и x_ {n + 1} = A x_ {n}, тов большом n-пределе x_ {n} / || x_ {n} ||приближается к нормированному собственному вектору, соответствующему наибольшему собственному значению.

Неквадратичные матрицы?

Заметив, что ваша система не является квадратной матрицей, я довольноУбедитесь, что задача SVD может быть разложена на отдельные задачи линейной алгебры, где будет применяться алгоритм Ланцоша.Хорошее место, чтобы задать такие вопросы, было бы в https://math.stackexchange.com/.