Aktualizacja diagonalna symetrycznej dodatniej określonej macierzy

$A$ jest symetryczną macierzą dodatnią z oznaczeniem dodatnim (SPD). jest rzadką macierzą diagonalną. jest duże ( > 10000), a liczba niezerowych w wynosi zwykle 100 ~ 1000. $n \times n$ $G$ $n$ $n$ $G$

$A$ Został factorized w Cholesky'iego postaci jako . $LDL^T$

Jak skutecznie zaktualizować i gdy staje się ? $L$ $D$ $A$ $A+G$

linear-algebra
źródło

Czy G ma tylko pozytywne elementy? Jeśli tak, oto trywialna górna granica: zobacz aktualizację diagonalną jako sumę aktualizacji rangi 1. Istnieją metody O (n ^ 2) do obliczenia faktoryzacji LDL ^ t aktualizacji 1-szej (wyszukiwarka Google podaje przykłady). Wtedy twoja aktualizacja po przekątnej będzie działać w O (rn ^ 2), gdzie r jest liczbą niezerowych elementów po przekątnej G. Biorąc pod uwagę specyfikę tych aktualizacji, istnieją skróty do zapisywania niektórych obliczeń, ale nie jest jasne, czy jest to możliwe zmniejsz kolejność poniżej O (rn ^ 2).

Zgadzam się - nie sądzę, aby można było zrobić diagonalne aktualizacje faktoryzacji Cholesky'ego szybciej niż tylko powtarzanie faktoryzacji, ale aktualizacje pierwszej rangi można wykonać w czasie , a ty musisz zrobić tylko jedną każdy niezerowe na przekątnej .

O (m^{2})

$O(m^2)$

G

$G$

Brian Borchers

Dla i w setki, to będzie trudne do pokonania refactoring . Jeśli rozmiar staje się znacznie większy, a jest bardzo rzadki, może się to opłacić. W każdym razie możliwe aktualizacje i aproksymacje są szczegółowo omówione przez Czy przekątna plus stałe symetryczne układy liniowe mogą zostać rozwiązane w kwadratowym czasie po wstępnym obliczeniu? .

n \sim 10^{4}

$n \sim 10^4$

n n z (G)

$\mathrm{nnz}(G)$

A

$A$

A

$A$

G

$G$

Jed Brown

Jed, myślę, że powinieneś promować swój komentarz do odpowiedzi tutaj.

Michael Grant

Odpowiedzi:

Najnowsza wersja pakietu CHOLMOD SuiteSparse (beta 4.4.5) obsługuje modyfikowanie symetrycznego wiersza / kolumny (aktualizacja Rank2) dla dekompozycji $LDL^T$ , przy użyciu interfejsu API Matlab (i C). Z powodzeniem wykorzystałem go w jednym z moich projektów.

Możesz go użyć do aktualizacji $nnz(G)$ do faktoryzacji. Opiera się na tym dokumencie.

Dlatego złożoność będzie wynosić $O(nnz(G)*nnz(L))$ . Gdzie $nnz(L)$ można znacznie zmniejszyć, stosując permutację zmniejszającą wypełnienie dla rzadkiego $A$

Pakiet można pobrać stąd

Poniżej kilka uwag właściciela pakietu (prof. Tim Davis):

API:

LD = ldlrowmod (LD, k) usuwa wiersz / kolumnę k, ustawiając A (:, k) i A (k, :) na k-ty wiersz / kolumnę tożsamości.

LD = ldlrowmod (LD, k, C) zastępuje k-ty wiersz / kolumnę A (który musi być k-tym wierszem / kolumną identyczności) rzadką kolumną C.

Złożoność:

Dodawanie / usuwanie wiersza zajmuje najwyżej czas $O(nnz(L))$ , więc jeśli $nnz(L)$ to $O(n)$ , wówczas czas wynosi najwyżej $O(n)$ .

Permutacja zmniejszająca wypełnienie:

Rzadko warto uwzględniać macierz użytkownika, tak jak w $LDL^T$ = A. Raczej permutujemy do $LDL^T$ = $PAP^T$ , aby $L$ miał znacznie mniej nonzerów.

Yuval Atzmon
źródło