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

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?

linear-algebra eigensystem 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.

X X^{T}

$XX^T$

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 .

X X^{T}

$XX^T$

O (n^{3})

$O(n^3)$

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:

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=XX^\mathsf{T}$ $x \leftarrow X(X^\mathsf{T}x)$ $A$ $\mathcal O(n^3)$ $\mathcal O(n^2)$

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

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

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

@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

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

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(X^Tx)$

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

$B = T = I$

hardmath

Não; Eu quis dizer o algoritmo padrão de Lanczsos, mas tinha pressa escrever CG. Agora corrigido.

Arnold Neumaier

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 em vez de . $A = XX^T$ $\mu$ $A - \mu I$ $A$

Algumas iterações do método básico de energia devem fornecer uma estimativa aproximada do maior autovalor . Supondo que o autovalor dominante tenha multiplicidade 1 e que todos os outros estejam em $||Ax||/||x||$ $\lambda_1$ , depois $[0,\frac{5}{6} \lambda_1]$ teria um maior autovalor $A - \frac{5}{12} \lambda_1 I$ e o resto em $\frac{7}{12} \lambda_1$ . $[\frac{-5}{12} \lambda_1, \frac{5}{12} \lambda_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, é estimado adicionando de volta a mudança que foi retirada. $A - \mu I$ $\lambda_1$ $\mu$

Observe que você não precisa formar explicitamente porque ainda pode ser calculado com esforço . $A - \mu I$ $(A - \mu I)x = X(X^Tx) - \mu x$ $O(n^2)$

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}

$\lambda_1$

| λ_{2} | / | λ_{1} |

$|\lambda_2|/|\lambda_1|$

| λ_{2} | / | λ_{1} |

$|\lambda_2|/|\lambda_1|$

λ_{2}

$\lambda_2$

λ_{1}

$\lambda_1$ se 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