Complexidade de encontrar a composição Eigend de uma matriz * simétrica *

9

Esta é uma versão especializada de uma pergunta anterior: Complexidade de encontrar a composição Eigend de uma matriz .

Para matrizes simétricas NxN, sabe-se que o tempo O (N ^ 3) é suficiente para calcular a decomposição do eigen. A questão é: podemos alcançar complexidade sub-cúbica? Obrigado.

ds.algorithms time-complexity matrices linear-algebra na.numerical-analysis Lihong Li
fonte
Isso realmente precisa de uma pergunta separada? Certamente, se alguém soubesse a resposta para esse caso especial, o teria dito na outra pergunta.
Warren Schudy
Eu enfatizei o pior caso na minha pergunta, então acho que isso é justo ...
Lev Reyzin
2
Você tem certeza do tempo limite O (N ^ 3)? Veja minha pergunta relacionada sobre a eliminação gaussiana.
Jeffε
Parece que em mathoverflow.net/questions/24287/… você pode obter para uma solução aproximada . O(n3)
Lev Reyzin

Respostas:

2

A meu ver, este caso especial não é mais fácil do que o caso geral. Puramente simbolicamente, você pode reduzir o problema de encontrar a decomposição de valor singular (SVD) ao problema de diagonalizar uma matriz simétrica. Pode-se ler o SVD de M a partir dos vetores próprios e dos valores próprios de M * M. Observe que a redução envolve apenas uma multiplicação de matrizes para calcular M * M. Parece que não deve haver problemas numéricos sérios.


fonte