Diagonalización de matrices densas mal condicionadas

Estoy tratando de diagonalizar algunas matrices densas y mal acondicionadas. En la precisión de la máquina, los resultados son inexactos (devuelve valores propios negativos, los vectores propios no tienen las simetrías esperadas). Cambié a la función Eigensystem [] de Mathematica para aprovechar la precisión arbitraria, pero los cálculos son extremadamente lentos. Estoy abierto a cualquier cantidad de soluciones. ¿Existen paquetes / algoritmos que se adapten bien a problemas mal condicionados? No soy un experto en preacondicionamiento, así que no estoy seguro de cuánto podría ayudar esto. De lo contrario, todo lo que puedo pensar son solucionadores de valores propios de precisión arbitraria paralelos, pero no estoy familiarizado con nada más allá de Mathematica, MATLAB y C ++.

Para dar algunos antecedentes sobre el problema, las matrices son grandes, pero no enormes (4096x4096 a 32768x32768 como máximo). Son reales, simétricos, y los valores propios están delimitados entre 0 y 1 (exclusivo), con muchos valores propios muy cerca de 0 y ninguno cerca de 1. La matriz es esencialmente un operador de convolución. No necesito diagonalizar todas mis matrices, pero cuanto más grande sea, mejor. Tengo acceso a clústeres informáticos con muchos procesadores y capacidades informáticas distribuidas.

Gracias

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

¿Qué rutina estás usando para diagonalizar tus matrices simétricas reales? ¿Y en qué sentido la descomposición del valor propio es inexacta?

Jack Poulson

Aquí hay una idea relacionada con la respuesta de Arnold: realice una descomposición de Cholesky de su matriz SPD, y luego encuentre los valores singulares del triángulo de Cholesky que acaba de obtener, posiblemente utilizando un algoritmo de tipo dqd para preservar la precisión.

@JM: La formación de la descomposición de Cholesky de una matriz definida positiva numéricamente singular es numéricamente inestable con el método habitual, ya que uno probablemente encuentra pivotes negativos. (Por ejemplo, el chol de Matlab (A) generalmente falla). Uno tendría que ponerlos a cero y aniquilar las filas correspondientes de los factores. Hacer esto proporciona una forma de obtener de manera confiable el espacio nulo numérico.

Arnold Neumaier

@Arnold, si la memoria sirve, hay adaptaciones de Cholesky que utilizan pivotante simétrica para los casos en que la matriz es positivo semi -definite (o casi). Quizás esos podrían usarse ...

@JM: Uno no necesita pivotar para resolver el caso semidefinido; La receta que di es suficiente. Solo quería señalar que uno no puede usar los programas enlatados estándar, sino que tiene que modificarlos uno mismo.

Arnold Neumaier

Respuestas:

Calcule la SVD en lugar de la descomposición espectral. Los resultados son los mismos en aritmética exacta, ya que su matriz es positiva simétrica positiva, pero en aritmética de precisión finita, obtendrá los valores propios pequeños con mucha más precisión.

Editar: Ver Demmel y Kahan, Valores singulares precisos de matrices bidiagonales, SIAM J. Sci. Stat. Comput 11 (1990), 873-912.
ftp://netlib2.cs.utk.edu/lapack/lawnspdf/lawn03.pdf

Edit2; Tenga en cuenta que ningún método podrá resolver valores propios más pequeños que aproximadamente la norma multiplicada por la precisión de la máquina, ya que el cambio de una sola entrada por un ulp ya puede cambiar un valor propio pequeño. Por lo tanto, obtener valores propios cero en lugar de valores muy pequeños es apropiado, y ningún método (excepto trabajar con mayor precisión) desenredará los vectores propios correspondientes, pero solo devolverá una base para el espacio nulo numérico común.

Arnold Neumaier
fuente

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

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

@JackPoulson: El punto es que la forma bidiagonal determina mucho mejor los valores singulares pequeños. La forma tridiagonal simétrica asociada tiene ceros en la diagonal, que se conservan mediante la reducción bidiagonal a diagonal, pero no mediante QR aplicado a la tridiagonal.

Arnold Neumaier

¿Referencia? Se sabe que el método de Jacobi es altamente preciso (aunque lento).

Jack Poulson

@JackPoulson: Intenta ver. Demmel & Kahan, Valores singulares precisos de matrices bidiagonales

Arnold Neumaier

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

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

Gracias por esta sugerencia. Intenté el comando SVD de Mathematica, pero no obtengo una mejora notable (todavía me faltan las simetrías apropiadas, los 'valores propios' son incorrectamente cero donde antes salían incorrectamente). ¿Quizás deba implementar uno de los algoritmos que describió anteriormente en lugar de una función incorporada? Probablemente quiera evitar tener que usar un método específico como este a menos que esté seguro de antemano de que ofrecerá una mejora significativa.

@JackPoulson, leí el documento sobre el método de Jacobi al que hizo referencia, y parece prometedor. ¿Puede usted o alguien recomendar una buena manera de implementar el método de Jacobi para encontrar sistemas propios? Supongo que si lo codificara yo mismo (en MATLAB), sería extremadamente lento.

Leigh
fuente

No lo he probado, pero hay una implementación de MATLAB aquí: groups.google.com/forum/?fromgroups#!msg/sci.math.num-analysis/…

Jack Poulson

Tenga en cuenta que ningún método podrá resolver valores propios más pequeños que aproximadamente la norma multiplicada por la precisión de la máquina, ya que el cambio de una sola entrada por un ulp ya puede cambiar un valor propio pequeño. Por lo tanto, obtener valores propios cero en lugar de valores muy pequeños es apropiado, y ningún método (excepto trabajar con mayor precisión) desenredará los vectores propios correspondientes, pero solo devolverá una base para el espacio nulo numérico común. ¿Para qué necesita los valores propios?

Arnold Neumaier

@ArnoldNeumaier: Realicé algunas pruebas en MATLAB con valores propios en el rango de [0,1], con un valor propio establecido manualmente en valores como 6.3e-16, y la rutina SVD de Octave (basada en dgesvd, que utiliza la reducción a bidiagonal y entonces QR) recoge estos valores con mucha más precisión que el eig de Octave. El código vinculado de Jacobi parece ser demasiado lento para usar, incluso en matrices de tamaño modesto.

Jack Poulson

@JackPoulson: Sí. Pero Leigh parece quejarse de múltiples valores propios muy pequeños, y sus vectores propios rara vez serán los diseñados, pero se mezclarán libremente, sin importar qué método se utilice. Y, por supuesto, los valores positivos muy pequeños (menores de 1e-16) se encontrarán en cero.

Arnold Neumaier

@ArnoldNeumaier tiene razón en que estoy encontrando múltiples valores propios muy pequeños, lo que supongo exacerba el problema. No me di cuenta (aunque en retrospectiva es obvio) que los valores propios inferiores a 1e-16 serán cero en coma flotante. Supongo que aunque se puede almacenar el número, se produce un error de redondeo al agregarlo a un número mayor. Los vectores propios me dicen si cierto problema es solucionable. El vector propio permite la descomposición del problema en partes solubles y no solucionables. Si la precisión me limita fundamentalmente, ¿puede recomendarme algún paquete para una solución más rápida?

Leigh