n × n G n n G es una matriz dispersa simétrica positiva definida (SPD). es una matriz diagonal escasa. es grande ( > 10000) y el número de nonzeros en suele ser de 100 ~ 1000.
L D L T ha sido factorizar en forma de Cholesky como .
¿Cómo actualizar y eficiente cuando convierte en ?D A A + G
Respuestas:
La última versión del paquete CHOLMOD SuiteSparse (beta 4.4.5) admite la modificación de una fila / columna simétrica (actualización de rango 2) para descomposición , utilizando una API matlab (y C). Lo usé con éxito en uno de mis proyectos.LDLT
Puede usarlo para realizar a la factorización. Se basa en este documento.nnz(G)
Por lo tanto, la complejidad será . Donde puede reducirse significativamente cuando se usa un relleno que reduce la permutación para un escasoO(nnz(G)∗nnz(L)) nnz(L) AA
El paquete se puede descargar desde aquí.
A continuación hay algunas notas que dio el propietario del paquete (Prof. Tim Davis):
API:
Complejidad:
Relleno que reduce la permutación:
fuente