Algoritmos para grandes matrices enteras dispersas

12

Estoy buscando una biblioteca que realice operaciones matriciales en grandes matrices dispersas sin sacrificar la estabilidad numérica. Las matrices serán 1000+ por 1000+ y los valores de la matriz estarán entre 0 y 1000. Realizaré el algoritmo de cálculo del índice, por lo que generaré vectores de fila (dispersos) de la matriz en serie. A medida que desarrolle cada fila, tendré que probar la independencia lineal. Una vez que complete mi matriz con el número deseado de vectores linealmente independientes, necesitaré transformar la matriz en forma escalonada reducida.

El problema ahora es que mi implementación utiliza la eliminación gaussiana para determinar la independencia lineal (asegurando la forma escalonada de filas una vez que se han encontrado todos mis vectores de fila). Sin embargo, dada la densidad y el tamaño de la matriz, esto significa que las entradas en cada nueva fila se vuelven exponencialmente más grandes con el tiempo, ya que se debe encontrar el mcm de las entradas iniciales para realizar la cancelación. Encontrar la forma reducida de la matriz exacerba aún más el problema.

Entonces, mi pregunta es, ¿hay un algoritmo, o mejor aún, una implementación, que pueda probar la independencia lineal y resolver la forma escalonada reducida de la fila manteniendo las entradas lo más pequeñas posible? Una prueba eficiente para la independencia lineal es especialmente importante ya que en el algoritmo de cálculo del índice se realiza con mucho más.

jgonagle
fuente

Respuestas:

5

Puede trabajar el módulo de varios números primos grandes para obtener los resultados del módulo de estos números primos, luego verifique si hay racionales con pocos dígitos suficientes que satisfagan estas congruencias. En caso afirmativo, puede verificar mediante una matriz-vector multiplicar si la aproximación encontrada es exacta. Esto puede convertirse en un algoritmo de decisión exacto.

101000

enlaces relacionados:
http://cs.ucsb.edu/~koc/docs/j21.pdf
http://dl.acm.org/citation.cfm?id=355767
http://dl.acm.org/citation. cfm? id = 355765

Arnold Neumaier
fuente