Diagonalização de matrizes densas e mal condicionadas

Estou tentando diagonalizar algumas matrizes densas e mal condicionadas. Na precisão da máquina, os resultados são imprecisos (retornando valores próprios negativos, os vetores próprios não possuem as simetrias esperadas). Eu mudei para a função Eigensystem [] do Mathematica para tirar proveito da precisão arbitrária, mas os cálculos são extremamente lentos. Estou aberto a qualquer número de soluções. Existem pacotes / algoritmos adequados para problemas mal condicionados? Como não sou especialista em pré-condicionamento, não tenho certeza de quanto isso poderia ajudar. Caso contrário, só consigo pensar em solucionadores de autovalores de precisão arbitrários paralelizados, mas não estou familiarizado com nada além do Mathematica, MATLAB e C ++.

Para dar uma idéia do problema, as matrizes são grandes, mas não enormes (no máximo de 4096 x 4096 a 32768 x 32768). Eles são reais, simétricos e os autovalores são limitados entre 0 e 1 (exclusivo), com muitos autovalores sendo muito próximos de 0 e nenhum próximo de 1. A matriz é essencialmente um operador de convolução. Não preciso diagonalizar todas as minhas matrizes, mas quanto maior eu puder, melhor. Eu tenho acesso a clusters de computação com muitos processadores e recursos de computação distribuída.

Obrigado

linear-algebra parallel-computing eigensystem precision dense-matrix Leigh
fonte

Que rotina você está usando para diagonalizar suas matrizes simétricas reais? E em que sentido a decomposição do autovalor é imprecisa?

Jack Poulson

Aqui está uma idéia relacionada à resposta de Arnold: faça uma decomposição de Cholesky da sua matriz SPD e encontre os valores singulares do triângulo de Cholesky que você acabou de obter, possivelmente usando um algoritmo do tipo dqd para preservar a precisão.

@JM: A formação do decomposição de Cholesky de uma matriz definida positiva numericamente singular é numericamente instável com o método usual, pois é provável que haja pivôs negativos. (Por exemplo, o chol (A) do Matlab geralmente falha.) Seria necessário defini-los como zero e aniquilar as linhas correspondentes dos fatores. Isso permite obter o espaço nulo numérico de maneira confiável.

Arnold Neumaier

@Arnold, se a memória servir, há adaptações de Cholesky que usam pivotamento simétrico para os casos em que a matriz é semi- definida indefinida positiva (ou quase isso). Talvez aqueles que poderiam ser usados ...

@JM: Não é necessário girar para resolver o caso semidefinido; a receita que dei é suficiente. Eu só queria salientar que não se pode usar os programas enlatados padrão, mas é necessário modificá-los.

Arnold Neumaier

Respostas:

Calcular o SVD no lugar da decomposição espectral. Os resultados são os mesmos na aritmética exata, pois sua matriz é definida positivamente simétrica, mas na aritmética de precisão finita, você obterá os pequenos autovalores com muito mais precisão.

Edit: Veja Demmel & Kahan, Valores Singulares Exatos de Matrizes Bidiagonais, SIAM J. Sci. Estado. Comput. 11 (1990), 873-912.
ftp://netlib2.cs.utk.edu/lapack/lawnspdf/lawn03.pdf

Edit2; Observe que nenhum método poderá resolver valores próprios menores que os tempos normais que a precisão da máquina usou, pois alterar uma única entrada por uma ulp já pode alterar um valor próprio pequeno por esse valor. Portanto, obter zero autovalores no lugar de valores muito pequenos é apropriado, e nenhum método (exceto trabalhar com maior precisão) irá separar os autovetores correspondentes, mas apenas retornar uma base para o espaço nulo numérico comum.

Arnold Neumaier
fonte

[0, B^{T}; B, 0]

$[0, B^T; B, 0]$

@JackPoulson: O ponto é que a forma bidiagonal determina valores singulares pequenos muito melhor. A forma tridiagonal simétrica associada possui zeros na diagonal, que são preservados pela redução bidiagonal para diagonal, mas não pelo QR aplicado ao tridiagonal.

Arnold Neumaier

Referência? O método de Jacobi é conhecido por ser altamente preciso (embora lento).

21812 Jack Poulson

@JackPoulson: Tente e veja. Demmel & Kahan, precisos valores singulares de Bidiagonal Matrizes, 202.38.126.65/oldmirrors/ftp.netlib.org/lapack/lawnspdf/...

Arnold Neumaier

[0, B^{T}; B, 0]

$[0,B^T; B,0]$

Obrigado por esta sugestão. Eu tentei o comando SVD do Mathematica, mas não obtive nenhuma melhoria perceptível (ainda faltando simetrias apropriadas, 'autovalores' são incorretamente zero, onde estavam incorretamente negativos antes). Talvez eu precise implementar um dos algoritmos que você descreve acima, em vez de uma função interna? Provavelmente, eu gostaria de evitar o trabalho de usar um método específico como este, a menos que tivesse certeza antecipada de que isso ofereceria uma melhoria significativa.

@JackPoulson, passei os olhos pelo artigo sobre o método de Jacobi que você mencionou e parece promissor. Você ou alguém pode recomendar uma boa maneira de implementar o método de Jacobi para encontrar sistemas eigensistemas? Eu estou supondo que se eu mesmo codificasse (no MATLAB), seria extremamente lento.

Leigh
fonte

Eu não testei isso, mas não é uma implementação MATLAB aqui: groups.google.com/forum/?fromgroups#!msg/sci.math.num-analysis/...

Jack Poulson

Observe que nenhum método poderá resolver valores próprios menores que os tempos normais que a precisão da máquina usou, pois alterar uma única entrada por uma ulp já pode alterar um valor próprio pequeno por esse valor. Assim, obter zero autovalores no lugar de valores muito pequenos é apropriado, e nenhum método (exceto trabalhar com maior precisão) irá separar os autovetores correspondentes, mas apenas retornar uma base para o espaço nulo numérico comum. Para que você precisa dos valores próprios?

Arnold Neumaier

@ArnoldNeumaier: Eu executei alguns testes no MATLAB com valores próprios no intervalo de [0,1], com um valor próprio definido manualmente para valores como 6.3e-16 e a rotina SVD da Octave (baseada em dgesvd, que usa redução para bidiagonal e então QR) pega esses valores com muito mais precisão do que o eig da Octave. O código Jacobi vinculado parece ser muito lento para usar, mesmo em matrizes de tamanho modesto.

21412 Jack Poulson

@JackPoulson: Sim. Mas Leigh parece reclamar de vários autovalores muito pequenos, e seus autovetores raramente serão aqueles projetados, mas se misturam livremente, independentemente do método usado. E valores positivos muito minúsculos positivos (menores que 1e-16) serão obviamente encontrados zero.

Arnold Neumaier

@ArnoldNeumaier está certo ao encontrar vários autovalores muito pequenos, o que acho que exacerba o problema. Não percebi (embora em retrospecto seja óbvio) que autovalores menores que 1e-16 serão zero em ponto flutuante. Acho que, embora o número possa ser armazenado, ocorre um erro de arredondamento ao adicioná-lo a um número maior. Os autovetores me dizem se um determinado problema é solucionável. O vetor próprio permite a decomposição do problema em partes solucionáveis e não solucionáveis. Se sou fundamentalmente limitado pela precisão, você pode recomendar algum pacote para uma solução mais rápida?

21430 Leigh