SVD para encontrar o maior autovalor de uma matriz 50x50 - estou perdendo quantidades significativas de tempo?

13

Eu tenho um programa que calcula o maior valor próprio de muitas matrizes simétricas de 50x50 realizando decomposições de valor singular em todas elas. O SVD é um gargalo no programa.

Existem algoritmos muito mais rápidos para encontrar o maior valor próprio ou a otimização dessa parte não daria muito retorno sobre o investimento?

Anna
fonte
Você poderia fornecer mais informações sobre suas matrizes, por exemplo, se alguma coisa for conhecida sobre sua estrutura, o intervalo de seus autovalores ou a semelhança entre si?
Pedro
É uma matriz de covariância ( ). O teste mostra que todos os valores autônomos, com exceção dos 5 maiores, são próximos de zero e que o maior autovalor é pelo menos ~ 20% maior que o segundo maior. Como existem muitos autovalores próximos de zero, suponho que o intervalo não seja importante? Pode ser redimensionado para qualquer intervalo. A escala que estou usando atualmente me oferece um intervalo de 150 ~ 200. XXT
Anna
Além disso, a matriz não é muito singular, portanto o problema SVD está bem condicionado.
Anna
Como é simétrico e positivo (semi) definido, você pode usar a fatoração de Cholesky em vez do SVD. A fatoração de Cholesky leva muito menos flops para calcular do que o SVD, mas ser um método exato ainda leva . XXTO(n3)
Ken
@ Anna: Você já experimentou alguma das muitas abordagens propostas aqui? Eu ficaria muito curioso para saber o que funcionou melhor na prática para você ... #
Pedro

Respostas:

12

Dependendo da precisão necessária para o maior autovalor, você pode tentar usar a Power Iteration .

Para seu exemplo específico, eu iria até o ponto de não formar explicitamente, mas computar em cada iteração. computação exigiria operações , enquanto o produto vetor de matriz requer apenas .A=XXTxX(XTx)AO(n3)O(n2)

A taxa de convergência depende da separação entre os dois maiores valores próprios, portanto, essa pode não ser uma boa solução em todos os casos,

Pedro
fonte
1
Se o maior valor próprio é 20% maior que o próximo, a iteração de energia deve convergir rapidamente (todos os outros valores próprios são amortecidos por um fator de 5/6 em cada iteração, para que você obtenha um dígito para cada 13 iterações.
Wolfgang Bangerth
2
Os métodos do subespaço de Krylov são estritamente melhores que os métodos de energia, pois contêm o vetor da iteração de energia com o mesmo número de iterações.
precisa
1
@JackPoulson: Sim, mas cada iteração é mais cara de calcular ... Realmente valeria a pena por um problema tão pequeno?
Pedro
@ Pedro: é claro, os matvecs exigem trabalho quadrático e o quociente de Rayleigh eigensolve e a expansão subsequente são triviais em comparação.
precisa
1
Despesas de código? Como o @JackPoulson abordou a questão, B. Parlett et al (1982) ("Estimando o maior valor próprio com o algoritmo de Lanczos") comparam método de potência, método de potência + aceleração Aitken e uma aplicação de Lanczos visando o maior valor próprio de um valor real pos simétrica (ou hermitiana). def. matriz. Eles concluem que o método Lanczos é mais eficiente se for necessária uma precisão modesta (do primeiro valor próprio em relação ao segundo) e é melhor para evitar erros de conversão.
hardmath
5

Se apenas 5 autovalores forem muito significativos, o algoritmo de Lanczsos com como multiplicação de vetores matriciais deve fornecer convergência linear rápida após 5 etapas iniciais, portanto, um autovalor maior com maior precisão e poucas iterações.X(XTx)

Arnold Neumaier
fonte
Você (@ArnoldNeumaier) está pensando em algo assim , adequadamente simplificado ( )? É interessante que ele dê uma aproximação diferente de Lanczos se um terceiro vetor for retido, no mesmo subespaço de Krylov. B=T=I
hardmath
Não; Eu quis dizer o algoritmo padrão de Lanczsos, mas tinha pressa escrever CG. Agora corrigido.
Arnold Neumaier
4

Para uma matriz semi-definida positiva como , pode valer a pena o esforço para acelerar a convergência com uma mudança de espectro . Isto é, um escalar adequado μ é escolhido e o método de alimentação é aplicada a um - μ I em vez de um .A=XXTμAμIA

Algumas iterações do método básico de energia devem fornecer uma estimativa aproximada do maior autovalor λ 1 . Supondo que o autovalor dominante tenha multiplicidade 1 e que todos os outros estejam em [ 0 , 5||Ax||/||x||λ1, depoisA-5[0,56λ1]teria um maior autovalor7A512λ1Ie o resto em[-5712λ1.[512λ1,512λ1]

Em outras palavras, você aumentaria a dominância do maior autovalor de 20% no próximo maior para 40% no próximo maior (valor absoluto de um) autovalor. A convergência geométrica do método de potência aceleraria de acordo. Uma vez que o maior valor próprio de é encontrado com precisão suficiente, λ 1 é estimado adicionando de volta a mudança μ que foi retirada.AμIλ1μ

Observe que você não precisa formar explicitamente porque ( A - μ I ) x = X ( X T x ) - μ x ainda pode ser calculado com o esforço O ( n 2 ) .AμI(AμI)x=X(XTx)μxO(n2)

hardmath
fonte
Isso parece exigir uma boa idéia de qual é a magnitude do segundo maior autovalor. Como você o aproximaria nesse caso?
Pedro Pedro
λ1|λ2|/|λ1||λ2|/|λ1|λ2λ1se desejado. Eu estava sugerindo que benefício você veria em um caso como Anna descreve em seus comentários abaixo da Pergunta.
precisa saber é o seguinte