python - pseudocodigo - ¿Cómo calcular el determinante de matriz dispersa escasa sin convertirlo en denso?
determinante de una matriz java (2)
Estoy tratando de descubrir el método más rápido para encontrar el determinante de matrices simétricas y reales dispersas en python. Usando el módulo scipy Sparse pero realmente sorprendido de que no haya una función determinante. Soy consciente de que podría utilizar la factorización de LU para calcular el determinante, pero no veo una forma fácil de hacerlo porque el retorno de scipy.sparse.linalg.splu es un objeto y no es valioso crear una matriz densa de L y U: I También puede hacer sp.linalg.det(A.todense()) donde A es mi matriz escasa y escasa.
También me sorprende un poco por qué otros no han enfrentado el problema de la computación determinante eficiente dentro de scipy. ¿Cómo se usaría splu para calcular el determinante?
Miré en pySparse y scikits.sparse.chlmod . Lo último no es práctico ahora para mí, necesita instalaciones de paquetes y tampoco está seguro de cuán rápido es el código antes de que me meta en todos los problemas. ¿Alguna solución? Gracias por adelantado.
Aquí hay algunas referencias que proporcioné como parte de una respuesta here . Creo que abordan el problema real que intentas resolver:
- notes para una implementación en la biblioteca Shogun.
- Erlend Aune, Daniel P. Simpson: estimación de parámetros en distribuciones gaussianas de alta dimensión , particularmente la sección 2.1 ( arxiv:1105.5256 )
- Ilse CF Ipsen, Dean J. Lee: Aproximaciones determinantes ( arxiv:1105.0437 )
- Arnold Reusken: aproximación del determinante de grandes matrices definidas positivas simétricas dispersas ( arxiv:hep-lat/0008007 )
Citando de las notas de Shogun:
La técnica habitual para calcular el término log-determinante en la expresión de probabilidad se basa en la factorización de Cholesky de la matriz, es decir, Σ = LLT, (L es el factor de Cholesky triangular inferior) y luego se usan las entradas diagonales del factor para calcular el registro (det (Σ)) = 2∑ni = 1log (Lii). Sin embargo, para matrices dispersas, como suelen ser las matrices de covarianza, los factores de Cholesky a menudo sufren de fenómenos de relleno, que no son tan escasos en sí mismos. Por lo tanto, para grandes dimensiones, esta técnica se vuelve inviable debido a un requerimiento de memoria masiva para almacenar todos estos coeficientes irrelevantes no diagonales del factor. Si bien se han desarrollado técnicas de ordenamiento para permutar las filas y columnas de antemano con el fin de reducir el relleno, por ejemplo, la reordenación del grado mínimo aproximado (AMD), estas técnicas dependen en gran medida del patrón de escasez y, por lo tanto, no se garantiza que den mejores resultados.
Sin embargo, investigaciones recientes muestran que al usar una serie de técnicas de análisis complejo, álgebra lineal numérica y coloración de gráficos codiciosos, podemos, sin embargo, aproximar el determinante logarítmico hasta una precisión arbitraria [Aune et. al., 2012]. El truco principal radica en la observación de que podemos escribir log (det (Σ)) como traza (log (Σ)), donde log (Σ) es el logaritmo de matriz.
La forma "estándar" de resolver este problema es con una descomposición gradual, pero si no estás preparado para usar ningún nuevo código compilado, entonces no tienes suerte. La mejor implementación de Cholesky es el CHOLMOD de Tim Davis, que está licenciado bajo la licencia LGPL y, por lo tanto, no está disponible en la versión adecuada (scipy es BSD).