Mise à jour diagonale d'une matrice définie positive symétrique

19

n × n G n n GUNE est une matrice clairsemée symétrique positive définie (SPD). est une matrice diagonale clairsemée. est grand ( > 10000) et le nombre de nonzeros dans le est généralement de 100 à 1000.n×ngnng

UNE a été factorisée sous la forme de Cholesky comme .LLT

Comment mettre à jour efficacement et lorsque devient ?D A A + GLUNEUNE+g


la source
G n'a-t-il que des éléments positifs? Si c'est le cas, voici une limite supérieure triviale: visualisez la mise à jour diagonale comme une somme des mises à jour de rang un. Il existe des méthodes O (n ^ 2) pour calculer la factorisation LDL ^ t d'une mise à jour de rang 1 (la recherche Google fournit des exemples). Ensuite, votre mise à jour diagonale s'exécutera en O (rn ^ 2) où r est le nombre d'éléments diagonaux non nuls de G. Compte tenu de la nature spécifique de ces mises à jour, il existe des raccourcis pour enregistrer certains calculs, mais il n'est pas clair s'il est possible de réduire l'ordre en dessous de O (rn ^ 2).
3
Je suis d'accord - je ne pense pas qu'il existe un moyen de faire des mises à jour diagonales d'une factorisation Cholesky plus rapidement que de simplement répéter la factorisation, mais les mises à jour de rang 1 peuvent être effectuées en temps , et vous ne devez en faire qu'une pour chaque valeur non nulle sur la diagonale de . GO(m2)g
Brian Borchers
10
Pour et n n z ( G ) dans les centaines, il sera difficile de battre refactorisation A . Si la taille de A devient beaucoup plus grande et que G est très rare, cela pourrait être payant. Dans tous les cas, les mises à jour et approximations possibles sont couvertes en profondeur par les systèmes linéaires symétriques diagonaux et fixes peuvent-ils être résolus en temps quadratique après le précalcul? . ndix4nnz(g)UNEUNEg
Jed Brown
5
Jed, je pense que vous devriez promouvoir votre commentaire en répondant ici.
Michael Grant

Réponses:

3

La dernière version du package CHOLMOD SuiteSparse (beta 4.4.5) prend en charge la modification d'une ligne / colonne symétrique (mise à jour rank2) pour la décomposition LLT , à l'aide d'une API matlab (et C). Je l'ai utilisé avec succès dans l'un de mes projets.

Vous pouvez l'utiliser pour effectuer des mises à jour nnz(g) de la factorisation. Il est basé sur cet article.

Par conséquent, la complexité sera O(nnz(g)nnz(L)) . Où nnz(L) peut être significativement réduit lors de l'utilisation d'une permutation de réduction de remplissage pour un A clairseméUNE

Le package peut être téléchargé à partir d' ici

Voici quelques notes que le propriétaire du paquet a données (Prof. Tim Davis):

API:

LD = ldlrowmod (LD, k) supprime la ligne / colonne k, en définissant A (:, k) et A (k, :) sur la kème ligne / colonne d'identité.

LD = ldlrowmod (LD, k, C) remplace la kième ligne / col de A (qui doit être la kième ligne / col d'identité) par la colonne clairsemée C.

Complexité:

O(nnz(L))nnz(L)O(n)O(n)

Remplissez la permutation réductrice:

LDLTLDLTPAPTL

Yuval Atzmon
la source