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

$A$ 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 \times n$ $G$ $n$ $n$ $G$

$A$ a été factorisée sous la forme de Cholesky comme . $LDL^T$

Comment mettre à jour efficacement et lorsque devient ? $L$ $D$ $A$ $A+G$

linear-algebra
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).

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 .

O (m^{2})

$O(m^2)$

G

$G$

Brian Borchers

Pour

dans les centaines, il sera difficile de battre refactorisation

. Si la taille de

devient beaucoup plus grande et que

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? .

n \sim 10^{4}

$n \sim 10^4$

n n z (G)

$\mathrm{nnz}(G)$

A

$A$

A

$A$

G

$G$

Jed Brown

Jed, je pense que vous devriez promouvoir votre commentaire en répondant ici.

Michael Grant

Réponses:

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 $LDL^T$ , à 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 clairsemé $A$

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:

$LDL^T$ $LDL^T$ $PAP^T$ $L$

Yuval Atzmon
la source