Je recherche un algorithme efficace pour trouver la plus grande paire propre d'une petite matrice complexe générale (non carrée, non éparse, non symétrique), A, de taille m x n. Par petite, j'entends que m et n sont typiquement compris entre 4 et 64 et généralement autour de 16, mais avec m non égal à n. Ce problème est facile à résoudre avec les algorithmes SVD généraux de LAPACK, c'est-à-dire gesvd ou gesdd. Cependant, comme je dois résoudre des millions de ces problèmes et que je n'ai besoin que de la plus grande paire propre, je cherche un algorithme plus efficace. De plus, dans mon application, les vecteurs propres seront généralement similaires dans tous les cas. Cela m'a conduit à étudier les méthodes basées sur l'itération d'Arnoldi, mais je n'ai trouvé ni une bonne bibliothèque ni un algorithme qui s'applique à ma petite matrice complexe générale. Existe-t-il un algorithme et/ou une bibliothèque appropriés ?
Réponses
Trop de publicités?
L'itération de Rayleigh a une convergence cubique. Vous pouvez également mettre en œuvre la méthode de la puissance et voir comment elles se comparent, puisque vous avez besoin de la décomposition LU ou QR de votre matrice.
http://en.wikipedia.org/wiki/Rayleigh_quotient_iteration
Suite au commentaire de @rchilton, vous pouvez appliquer cela à A* A.
L'idée de rechercher la plus grande paire propre est analogue à la recherche d'une grande puissance de la matrice, car les modes de basse fréquence sont amortis au cours de l'itération. Le site Algorithme de Lanczos est l'un des quelques algorithmes de ce type qui s'appuient sur les vecteurs propres de Ritz pendant la décomposition. De Wikipedia :
L'algorithme de Lanczos est un algorithme itératif ... qui est une adaptation des méthodes de puissance pour trouver les valeurs propres et les vecteurs propres d'une matrice carrée ou la décomposition de la valeur singulière d'une matrice rectangulaire. Il est particulièrement utile pour trouver les décompositions de très grandes matrices éparses. Dans l'indexation sémantique latente, par exemple, les matrices reliant des millions de documents à des centaines de milliers de termes doivent être réduites à la forme de valeur singulière.
La technique fonctionne même si le système est pas clairsemée, mais si elle est grande et dense, elle a l'avantage de ne pas devoir être stockée en mémoire en même temps.
Comment cela fonctionne-t-il ?
La méthode de puissance pour trouver la plus grande valeur propre d'une matrice A peut être résumée en notant que si x_{0} est un vecteur aléatoire et x_{n+1}=A x_{n}, alors dans la grande limite n, x_{n} / ||x_{n}|| se rapproche du vecteur propre normé correspondant à la plus grande valeur propre.
Matrices non carrées ?
Étant donné que votre système n'est pas une matrice carrée, je suis presque sûr que le problème de l'UDS peut être décomposé en problèmes d'algèbre linéaire distincts où l'algorithme de Lanczos s'appliquerait. Un bon endroit pour poser de telles questions serait le site suivant https://math.stackexchange.com/ .
