Complexité de la recherche de la composition eigend d'une matrice

40

Ma question est simple:

Quel est le temps d'exécution le plus défavorable du meilleur algorithme connu pour calculer une composition simple d'une matrice ?n×n

Eigendecomposition réduit-il à la multiplication matricielle ou les algorithmes les plus connus (via SVD ) sont-ils dans le pire des cas?O(n3)

Veuillez noter que je demande une analyse du cas le plus défavorable (uniquement en termes de ), et non des limites avec des constantes dépendantes du problème, telles que le numéro de condition.n

EDIT : Compte tenu de certaines des réponses ci-dessous, laissez-moi ajuster la question: Je serais heureux avec une approximation de . L’approximation peut être multiplicative, additive, d’entrée, ou toute définition raisonnable que vous voudriez. Je suis intéressé s’il existe un algorithme connu qui dépend mieux de que de quelque chose comme ?n O ( p o l y ( 1 / ε ) n 3 )εnO(poly(1/ε)n3)

EDIT 2 : Voir cette question connexe sur les matrices symétriques .

Lev Reyzin
la source
Avez-vous examiné la réduction de l'inversion matricielle à la multiplication matricielle dans le manuel d'algorithmes CLRS? Je commencerais par examiner ces idées pour voir si elles s'étendent à la décomposition propre.
Warren Schudy
Oui, ils semblent aller jusqu'à trouver une décomposition de LU, mais je ne sais pas comment le faire fonctionner pour une décomposition propre.
Lev Reyzin
Savez-vous si O(n3) est l'algorithme le plus connu pour calculer le SVD?
Robin Kothari
1
n × nO(min(mn2,m2n))n×n
Bien. Je ne connais pas grand chose à propos de ce domaine non plus, mais le calcul de SVD peut peut-être être réduit à une composition eigend, car si vous pouvez eigend composer AA * et A * A, vous obtiendrez les matrices droite et gauche du SVD.
Robin Kothari

Réponses:

18

Ryan a répondu à une question similaire sur mathoverflow. Voici le lien: mathoverflow-answer

Fondamentalement, vous pouvez réduire le calcul des valeurs propres à la multiplication matricielle en calculant un déterminant symbolique. Cela donne un temps d'exécution de O ( ) pour obtenir bits des valeurs propres; le meilleur temps d'exécution actuellement connu est O ( ) pour une approximation à l'intérieur de .m n 3 + n 2 log 2 n log b 2 - bnω+1mmn3+n2bûche2nbûcheb2-b

Ryan parle de «Victor Y. Pan, Zhao Q. Chen: La complexité du problème propre à la matrice. STOC 1999: 507-516 ".

(Je crois qu'il y a également une discussion sur la relation entre la complexité des valeurs propres et la multiplication de matrices dans les anciens livres de Aho, Hopcroft et Ullman, "La conception et l'analyse d'algorithmes informatiques", cependant, je n'ai pas le livre dans devant moi, et je ne peux pas vous donner le numéro de page exact.)

virgi
la source
13

La recherche de valeurs propres est par nature un processus itératif: la recherche de valeurs propres équivaut à la recherche des racines d'un polynôme. De plus, le théorème d'Abel – Ruffini stipule qu'en général, vous ne pouvez pas exprimer les racines d'un polynôme arbitraire sous une forme fermée simple (c'est-à-dire avec des radicaux comme la formule quadratique). Ainsi, vous ne pouvez pas espérer calculer les valeurs propres "exactement".

Cela signifie qu'un algorithme de décomposition spectrale doit être approximatif. La durée d'exécution de tout algorithme général doit dépendre de la précision souhaitée. cela ne peut pas dépendre de la dimension.

Je ne suis pas un expert en la matière. Je suppose qu'une dépendance cubique sur n est très bonne. Les algorithmes que j'ai vus utilisent tous la multiplication matrice-vecteur, plutôt que la multiplication matrice-matrice. Je serais donc un peu surpris si tout se résume à la multiplication matrice-matrice.

Consultez http://en.wikipedia.org/wiki/List_of_numerical_analysis_topics#Eigenvalue_algorithms

Thomas
la source
Merci pour votre réponse - il me faudra du temps pour le digérer! Mais si on utilise la multiplication matrice-vecteur, la dépendance à n pourrait peut-être être meilleure que n ^ 3.
Lev Reyzin
6

Je ne donnerai qu'une réponse partielle concernant les valeurs propres d'une matrice.

Comme mentionné précédemment, il existe de nombreuses méthodes itératives pour trouver les valeurs propres d'une matrice (par exemple, une itération de puissance), mais en général, la recherche des valeurs propres se réduit à la recherche des racines du polynôme caractéristique. Trouver le polynôme caractéristique peut être fait en , où est le coût de bit multiplications et est la taille de bits de l'entrée maximale, par calcul de déterminant symbolique utilisant l'algorithme de Bareiss . Voir le livre de Yap sur les "Principes de base de l'algèbre algorithmique" , en particulier le Chap. 10, "Systèmes linéaires" .M B ( s ) s LO(n3MB[n(logn+L)])MB(s)sL

Une fois que le polynôme caractéristique est trouvé, on peut trouver les racines avec n'importe quel degré de précision souhaité en utilisant des intervalles d'isolation. Voir le livre de Yap, Chap. 6 "Racines de Polynômes" pour plus de détails. J'oublie le temps d'exécution exact mais son polynôme dans le degré du polynôme caractéristique et les chiffres de précision souhaités.

Je soupçonne que le calcul des vecteurs propres, quel que soit le degré de précision, est également polynomial, mais je ne vois pas d'algorithme simple. Il y a bien sûr le paquet d'astuces standard qui a été mentionné précédemment, mais pour autant que je sache, aucune d'elles ne garantit un temps d'exécution polynomial pour la précision désirée.

utilisateur834
la source
intéressant, mais cela semble même pire que n ^ 3. Savons-nous que c'est le meilleur possible?
Lev Reyzin
Les temps d'exécution sur des algorithmes de cette nature sont liés à la complexité de la multiplication de matrices qui est d'environ O (n ^ 3). Je connais l'algorithme de Strassen, mais si vous n'ignorez pas les problèmes de stabilité numérique, alors je pense que vous obtenez O (n ^ 3) pour la multiplication de matrices. Les méthodes itératives peuvent converger plus rapidement dans le cas "moyen", mais je pense qu'en général, environ 0 (n ^ 3) est ce que vous pouvez faire de mieux.
user834
Donc, vous dites que si je me moque des problèmes de stabilité numérique, on peut le réduire à O (n ^ 2.376)?
Lev Reyzin
5

Vous pouvez consulter le nouveau document de Commandur et Kale qui donne un algorithme combinatoire pour Max-Cut. Il semble (à partir d'une lecture rapide) que leur algorithme soit basé sur la recherche combinatoire du vecteur propre correspondant à la valeur propre maximale, puis sur l'utilisation de l'algorithme de Luca Trevisan une fois qu'ils ont ce vecteur propre.

Il semble qu'ils utilisent une approche alternative à l'algorithme de Lanczos pour trouver un tel vecteur propre, donc cela pourrait être intéressant. Je ne sais pas quelle est la complexité alléguée de leur méthode de recherche du vecteur propre, mais cela vaut peut-être la peine. De plus, comme il s’agit d’un rapport d’approximation et non de temps en soi qui les intéresse, les délais qu’ils donnent ne sont pas nécessairement optimaux.

astérix
la source
1

C'est une vieille question, mais certains ouvrages importants semblent avoir été oubliés.

(Oω+η)ωη>0

Oui, il y a le papier Pan + Chen + Zheng qui suggère d'assembler le polynôme caractéristique et de calculer dans BigFloat parce que vous perdez beaucoup de précision à la fin, mais peu de gens considéreraient cela comme une approche pratique.

Je mentionne également que l'algorithme le plus largement utilisé, l'itération Francis QR, n'a aucune preuve de convergence pour les matrices générales; Le livre de Kressner traite de plusieurs contre-exemples.

Sébastien Loisel
la source
0

Oui, presque toute l’algèbre linéaire numérique peut être réduite à la multiplication matricielle, bien que, comme toujours, la stabilité numérique soit un problème. De plus, avec des problèmes tels que eigendecomposition, vous devriez vous contenter d'une approximation car la solution peut être irrationnelle. Consultez le livre Calculs polynomiaux et matricaux de Bini et Pan.

Voici une autre référence - L'algèbre linéaire rapide est stable http://www.netlib.org/lapack/lawnspdf/lawn186.pdf

Anonyme
la source
3
Merci pour le pointeur, mais en effectuant une recherche dans le livre sur Google Books, je n’ai pas trouvé la réduction à la multiplication matricielle. Avez-vous un pointeur sur une référence concrète ou un algorithme? Et leurs algorithmes SVD semblent dépendre du nombre de conditions de la matrice, ce qui n’est pas une analyse dans le pire des cas. En ce qui concerne les problèmes de stabilité numérique, etc., supposons le cas idéalisé, où toutes les multiplications et divisions prennent le temps unitaire et produisent des réponses exactes.
Lev Reyzin