Complexité de la recherche de la composition à base d'une matrice * symétrique *

9

Il s'agit d'une version spécialisée d'une question précédente: Complexité de la recherche de la composition par matrice d'une matrice .

Pour les matrices symétriques NxN, il est connu que le temps O (N ^ 3) suffit pour calculer la décomposition propre. La question est: pouvons-nous atteindre une complexité sub-cubique? Merci.

ds.algorithms time-complexity matrices linear-algebra na.numerical-analysis Lihong Li
la source
Cela nécessite-t-il vraiment une question distincte? Sûrement, si quelqu'un avait su la réponse à ce cas particulier, il l'aurait dit dans l'autre question.
Warren Schudy
J'ai souligné le pire des cas dans ma question, donc je pense que c'est juste ...
Lev Reyzin
2
Êtes-vous sûr de cette limite de temps O (N ^ 3)? Voir ma question connexe sur l'élimination gaussienne.
Jeffε
Il semble que mathoverflow.net/questions/24287/… vous pouvez obtenir pour une solution approximative . O(n3)
Lev Reyzin

Réponses:

2

Selon moi, ce cas particulier n'est pas plus facile que le cas général. De manière purement symbolique, vous pouvez réduire le problème de la découverte de la décomposition en valeurs singulières (SVD) au problème de la diagonalisation d'une matrice symétrique. On peut lire la SVD de M à partir des vecteurs propres et des valeurs propres de M * M. Notez que la réduction n'implique qu'une multiplication matricielle pour calculer M * M. Il ne semble pas qu'il y ait de sérieux problèmes numériques.


la source