Я ищу эффективный алгоритм для поиска наибольшей собственной пары небольшой, общей (неквадратной, неразреженной, несимметричной) сложной матрицы A размером m x n. Под малым я подразумеваю m и n, как правило, между 4 и 64 и обычно около 16, но m не равно n. Эту проблему легко решить с помощью общих алгоритмов LAPACK SVD, то есть gesvd или gesdd. Однако, поскольку я решаю миллионы таких задач и мне нужна только самая большая собственная пара, я ищу более эффективный алгоритм. Кроме того, в моем приложении собственные векторы обычно будут одинаковыми для всех случаев. Это побудило меня исследовать методы, основанные на итерациях Арнольди, но я не нашел ни хорошей библиотеки, ни алгоритма, которые применимы к моей небольшой общей сложной матрице. Есть ли подходящий алгоритм и/или библиотека?
Эффективный алгоритм нахождения наибольшей собственной пары малой общей комплексной матрицы
Ответы (2)
Итерация Рэлея имеет кубическую сходимость. Вы можете также реализовать метод мощности и посмотреть, как они сравниваются, поскольку вам нужна LU или QR-разложение вашей матрицы.
http://en.wikipedia.org/wiki/Rayleigh_quotient_iteration
Следуя комментарию @rhilton, вы можете применить это к A * A.
Идея поиска наибольшей собственной пары аналогична поиску большой степени матрицы, поскольку низкочастотные моды затухают во время итерации. алгоритм Ланцоша — один из немногих таких алгоритмов, основанных на так называемых собственных векторах Ритца. во время разложения. Из Википедии:
Алгоритм Ланцоша — это итерационный алгоритм, который представляет собой адаптацию степенных методов для нахождения собственных значений и собственных векторов квадратной матрицы или разложения по сингулярным числам прямоугольной матрицы. Это особенно полезно для нахождения разложений очень больших разреженных матриц. Например, при латентном семантическом индексировании матрицы, связывающие миллионы документов с сотнями тысяч терминов, должны быть приведены к форме единственного числа.
Этот метод работает, даже если система не разрежена, но если она большая и плотная, то ее преимущество заключается в том, что ее не нужно хранить в памяти одновременно.
Как это работает?
Степенной метод нахождения наибольшего собственного значения матрицы A можно обобщить, отметив, что если x_{0} является случайным вектором и x_{n+1}=A x_{n}, то в пределе больших n x_{ n} / ||x_{n}|| приближается к нормированному собственному вектору, соответствующему наибольшему собственному значению.
Неквадратные матрицы?
Отметив, что ваша система не является квадратной матрицей, я почти уверен, что проблема SVD может быть разложена на отдельные задачи линейной алгебры, к которым применим алгоритм Ланцоша. Лучше всего задавать такие вопросы по адресу https://math.stackexchange.com/.
